I wouldn't trust anything that's not in writing. These are (assumably) relatively new companies to you; they don't know you and you don't know them. It's just too easy for something to go wrong: for example, you get an offer from a company that you believe is bonne fide, but while you are in the process of relocating, they retract the offer. I'm not saying that's likely; I'm just saying that if it's not in writing, I would keep an arm's length from actually making a financial investment into the relocation.
Personally, if they offer you a job (officially) by e-mail, I would request a written and signed job offer in the mail, which, as @PatriciaShanahan says, you could sign and return.
In fact, I might even go so far as to request two; one to keep on hand and one to send back. That might be a bit superfluous, though, as you could make a photocopy or something of that sort, which though perhaps not as official, is at least a hard copy.
It's far easier to send something off by e-mail than to mail it; it's also generally less legally binding, as e-mails tend to be frowned on in some courts. If the company is serious about hiring you, printing, signing, and mailing an official offer is no big trouble, especially if you've already confirmed (by e-mail) that you will sign the contract when it arrives.