JohnFx provides some good advice. Here's one more idea:
If you can't get a regular credit card without a long enough credit history, one tool that could be useful in speeding things up is a secured credit card. Secured credit cards are offered by some (but not all) banks and credit unions.
They work essentially like this: You put some money on deposit with the institution to guarantee your credit card debt. They'll give you a credit card with a matching credit limit. Other than the cash required to secure the card debt (if you default on your payments), it works like a regular credit card in that your monthly payments are typically reported to credit bureaus, which helps establish a credit history.
Once you've got an adequate credit history, you can apply for a regular credit card.
Things will also get easier once your work history is well-established.