The theory behind this is actually simple.
Basically, you just have to install a script/ software to run on your host account. The script can be written in any server-side scripting language or other programming language (Perl, PHP, ASP, Java, C/C++, etc).
Hotmail for instant, is written in Perl, running on Linux (it's labeled as MSN funny huh?). The squirrelmail recommended by davet is written in PHP.
Having that said, it's not hard to install a webmail service, but how you configure and the measures taken to avoid security breach are more of concern, if you want to provide a webmail service to public. Although at this point many don't foresee any good by offering this free webmail service anymore, unless for marketing purposes which may or may not generate too much profits. People tend to install webmail for their internal usage (such as LAN, be it in a campus, office, an organization, ...)
If you need more technical opinion on how to install and configure the webmail, then you should approach somebody who has experience to do it for you. Or else you are ready to face a steeper learning curve ahead, if you want to do it yourself. But it certainly worths lots more than the effort you've put in.