Copy'n'paste:
You want to switch completely to Gmail, but you want all your email in one place? Gmail's robust searching functionality is a great feature, but only if you can search through all your email in one place, not just email you have received since you switched. Follow these instructions to import your archived or saved email from Outlook into your Gmail account.

http://wiki.ehow.com/Import-Archived-Outlook-Email-Into-GMail-Using-GML

HTH

That may help many of my customers make the switch! Unfortunately, we still have the issue of many of them having many gigs of E-mail to import which would not exactly work with Gmail. Course, maybe that'll change 4/1!

Tell them to delete their "funny-videos". Or just copy&link to video.google.com.
And you want to upload gigabytes of email data to gmail?