A simple website lets you submit invites, and let you request an invite to use Gmail. So if you’re looking to get one for free, head on over to gmail invite spooler. I just gave them 100 invites to hand out, as I’ve already given numerous invites to Gmail4Troops.
Update: The Gmail invite is no longer necessary. You can sign up for Gmail using your mobile phone. Why the mobile phone? To ensure you’re a legitimate person, and to prevent spammers from signing up and abusing their service.