Get Rich Slowly - Personal Finance That Makes Cents covers this stuff on a real regular basis. My 2 cents, get a credit card, any card you can that doesn't have an annual fee, ignore the interest rate.
Buy something for $100 or so, sneakers, clothing, whatever. Then fill up your car once a month on that credit card. Pay off the gas charge each month + an extra $10 towards the initial $100 deposit.
This shows that you 1. can make payments and 2. continue to use the card each and every month. Not paying the balance in full shows you can "give" money to the credit card company and still not mis a payment.
Speaking of, do not ever miss a payment your first two years of having a card, no matter what!
Personally, I carry an AMEX blue card, easy cash back, no stupid points or miles, I don't spend enough on my card to actually get 40k miles for a free $150 voucher for an airline.
I also carry AMEX because nearly every bank I've had with Visa has screwed me, but I will say I'd take AMEX or Visa over Mastercard any day, if for nothing else, the doubling of any warranty up to a year past the factory one is golden. Saved my rear on a $3k digital camera a few years back + means I rarely ever have to think about buying any extended warranty from a store. Additionally, my AMEX blue (can't speak for the rest) will refund me up to $300 (I think, have to double check) on any item that a store refused to return / refund for me. Haven't had to use it yet, but it's nice to know it's there.