For folks who do not have exactly this situation, the easiest way to boostrap up a US credit card history is to go to the bank you have direct deposit with (they have the most reason to like you) and ask to open a secured card. They will open a special savings account and require you to fund it, generally to the tune of $500. That account is then frozen: it continues to accrue (pitiful) interest, but you can't withdraw it. They will simultaneously issue you a credit card with a $500 limit. It is exactly like every other credit card: you pay interest if you revolve balances, it has to be paid on time, and it reports to the credit bureaus.
After 6 to 12 months of "good behavior", they will a) unfreeze your deposit and b) "upgrade" the credit card from a secured card to one of their standard beginning product lines. Expect something like a $2,000 limit at a fairly unfavorable interest rate, much like you'd get if you were a college student.
Continue periodically buying a stick of gum on that card and paying it when it is due, and you'll have 800 FICO within about two years.