Push e-mail is when your phone gets notified that you have a new message without having to go check for it.
An example would be corporate e-mail through Microsoft Exchange. If you have outlook running at your desk, when you get a new e-mail message in your mailbox on the exchange server, it appears in outlook automatically. You can also force outlook to manually check for new messages, but you are notified automatically of messages and appointments without you having to check to see if you have new ones.
With push e-mail set up on an iPhone, if someone sends me an e-mail, it shows up on my phone even if I have mail check set to "manual".
Gmail and Cox don't support "push", so you have to check those mailboxes manually using the iPhone's mail app.
Exchange and Mobile Me (and to a certain extent Yahoo) are the ones that support push.
In short it breaks down like this -
Push = mail comes to your phone without any interaction required from you
Fetch = Your phone goes to look for new mail either at a set interval or when you manually check your messages