Here's a
link to a site that walks you through email setup. The Pocket PC version of Outlook can be a bit finicky and it seems like it got worse in Pocket PC 2003. It may just be a setting or something. I find that removing everything, soft resetting and starting from scratch will fix a lot of problems.
I don't know about Gmail. I know that the Pocket PC version of IE has problems with a lot of web based mail so it may or may not work. If it's like Yahoo, you may have to forward your mail in order for it to work. Yahoo charges for that service, don't know if Google will.