It's not difficult, but it's a slow process. I started out by getting a mail-order account and a store card. Once I had those established, I went for a credit card. Some banks will give you a credit card when you open an account -- but that varies from bank to bank.
Also, from what I understand, credit history is closely linked to address history here, so obviously, since my address is the same as my husband's, I can kind of "feed" off of his good credit. My mail-order account was opened about a month after I got here and they gave me a very generous limit based on my husband's credit history (though his name is not at all associated with the account).