There seems to be a lot of misconceptions on what is actually reported to the credit bureaus that makes up a person's credit history. (This will all be US-centric information.)
There are two components to someone's credit history: the credit report and the credit score.
When talking about a credit history in an absract way, people are almost always talking about the reports compiled by the three credit bureaus: Equifax, TransUnion, and Experian. They compile information on any credit that is extended to you. This can include car loans, student loans, personal loans, credit cards, mortgage loans, HELOCs, and other lines of credit. They also include information from any collection agencies that may be pursuing debts.
For the most part (there are a few exceptions), utilities, phone companies, and landlords do not report to credit bureaus. If you are delinquent to any of these folks, though, you will generally be turned over to a collections agency, and that agency will report you to the credit bureaus. So paying on time to any of these places won't help your credit history, but not paying will hurt you.
Most utilities, phone companies, and banks have their own systems that report your payment history within the narrow scope of their services. For instance, if you overdraw your bank account too frequently, your history will be recorded in ChexSystems and you could be denied opening a checking account at other banks. But if you check your credit report, these items most likely will not be on it.
Now to the credit score. The credit score is generated from the information from your credit report. Things that improve your score will be a low debt-to-credit ratio, number of accounts (but not too many!), age of accounts, mix of accounts, and payment history. Things that can hurt you are a high debt-to-credit ratio, too few accounts, not a very long history, a history of delinquent payments, and too many credit inquiries (so-called "hard pulls," which do not include viewing your own credit report, and multiple queries within a very short time frame are often viewed as just one pull). Your score won't take too hard of a hit from hard pulls, and will often rebound in just a few months.
Edited to add: having store credit cards can hurt your score as well
As someone said before, scores range from 300 to 850. Scores are mostly used to determine what kind of an interest rate you qualify for. (The better the score, the lower the interest rate.). Credit scores are not provided to employers who are making hiring decisions. They can obtain a credit report (and only with your permission), but not a score. Additionally, the report is somewhat different than the report provided to lenders.
I think landlords can get your score, although I'm not really sure about that. Many landlords will only want the credit report anyway.
For the most part, negative information stays on your credit report for 7 years. There are exceptions, such as bankruptcy, which stays on for 10 years. However, even if negative information hasn't aged off your report, your score can improve as time passes and you make on-time payments.