Gmail/Invite a friend
Look on the left options bar. You will see links to compose messages, go to the inbox, view a particular label, etc. Down at the bottom, right below the label box, is the invite box. This tells you how many invites you have left and provides a box in which you can put an email address. Just put the email address of the recipient and click Send Invite.
Your GMail account may not have this box enabled, however. If there is no Invite box available, Google advises you to "be patient", as they randomly allow some users to issue invites, and other users must wait. Finally each user only has a limited number of invites they are able to offer at any given time, and you may need to wait for further invites to be available.
Right now, every user can invite, but in fact this is not needed. GMail is now available for everyone and everybody can register.