I installed today from Market, the Yahoo Mail application and I was reading it offers push message notification technique. Indeed it works, as I got exactly the same moment the alert on my desktop computer and my mobile mail client.
How is it accomplished?
Without installing the app, setting up my router to capture packets, and doing some packet inspection I can't tell you exactly how they do it. At the lowest level it's as simple as keeping an open TCP connect to a remote server and having the server sending the client a packet when it needs to do something. My educated guess on the specific way they are doing it is either with IMAP IDLE, or XMPP.
Soon, you will be able to use the Cloud-to-Device Messaging (C2DM) system, though it will require Android 2.2 or higher. You might also want to watch the Google I|O 2010 conference presentation on it, which gives a few clues as to how they implemented it.
There already is another question discussing how to implement push notification without the cloud to device messaging in older system.
There are several frameworks that give you push abillity. They all require a running a small background thread that is polling a server at a very short interval(Bad for data rate and battery) or keep an open connection to a server that is kept alive somehow and the client is notified every time a new message is waiting on the server.
Have a look at the question and maybe choose on of the mentioned frameworks, the frameworks will reuse the same service for all applications that are installed on the phone using the same framework and therefore save battery and general system usage.