Disclaimer
First off, I'm not saying anything new that hasn't been said. Most people already stated the obvious and the simplest way is to have an e-mail client installed. Since this post is already too long I'll just link to step by step instructions around the web for each part that's relevant. If the links are broken, I'm sure you can search for new ones if you have the right keywords.
Also I use mostly Mac and only Gmail, so I have no self knowledge of other webmail today even while I've used them in the past and actually still have yahoo and hotmail accounts.
The Methods
There are basically 3 things you can do to backup e-mails from Gmail and many sub-options. As far as I know, there are just 2 things you can do, with no sub-options, on Yahoo and any other free webmail service.
Also except on Gmail (and maybe on Yahoo while YPOPS! works) you'll have to pay to be able to get the messages out there anyway.
(1). Using a software to retrieve e-mails to your machine, or even the whole webmail configuration
(2). Forwarding your e-mails as they arrive to any number of other places
(3). Using the webmail options
I'll discuss briefly each method and you can even use both at same time if so you wish.
(1). Retrieving from the webmail
You can do this in 2 different ways and once it's done you still can take another step of backup by using any backup method for your regular local files (files on your machine). This is not directly backing up webmail files, but you should be doing this already way before backing up your webmail. I myself do local backup of everything and online backups of important stuff.
As a side note, in general you'll hardly have over 10GB of emails, and most machines today come with at least 160GB of hard disk. You'll most likely have used at least 20GB of your machine space for regular stuff, if you don't save too much music, pictures or videos. So you'll most likely have 140GB free space for backing up your e-mail. Those are rough numbers, but in general you won't have to worry too much on backing up emails locally in your machine.
(1.A). Using regular mail client
keywords: mail backup
You can get Mozilla Thunderbird (either for Windows Mac or Linux) or any other mail client. Mail from Apple is great, Mozilla is quite default on Linux but I highly advice against Outlook Express - get Outlook if you must. In general if you want security and less bugs you have to get away from main stream, and that is Microsoft today. There's also Opera Mail, also for every platform, but that's quite techy. I highly advise using Thunderbird. There are enough step by step instructions online for installing it and configuring it with each webmail you wish:
Installing Thunderbird official link: http://www.mozilla.org/support/thunderbird/faq#install (it's just download and click click, really)
Configuring Gmail on TB: http://mail.google.com/support/bin/answer.py?hl=en&answer=38343
Configuring Yahoo on TB: http://answers.yahoo.com/question/index?qid=20100110124707AAVwbX1
Others for TB: http://kb.mozillazine.org/Creating_accounts_in_Thunderbird_for_popular_email_providers
Either configuring POP, which is the simplest way, or IMAP, which can be accomplished and will save more info about your mailbox but it's a LOT harder to setup, you will mostly be backing up your mails only. If you ever want to restore them to your webmail, you'll have a lot of work to do (either hosting mail server on your machine or pushing the files to a server somehow), it won't be easy at all, and you won't get your webmail configurations back - if you have any. That's why the method B might be suitable for you, and you can, once again, even use both - just remember you'll need double the space on your machine.
(1.B). Using specific software for each webmail
keywords: mail backup restore
While this is easy to setup, it's highly dependable on the software rather than on standard protocols, so it's good while it exists and has fairly uncertain future (although your backup won't ever be lost and will be searchable within your own machine). So this isn't really a solution for most webmails. Even on Gmail things can get ugly to restore.
I only know a Gmail option here the "Gmail Backup". It saves not only the mail messages, but also your configurations, like labels. And, more importantly, it is able to restore your emails back to the webmail, or even into another account if you so wish:
http://www.gmail-backup.com/
(2). Forward email to another server
keywords: mail forward
Make no mistake, forwarding have to be to another server - not your machine. Let's say you have name@gmail.com and name@yourisp.com if you configure gmail to forward to yourisp and you think you're getting them on your machine, that's because it first goes to yourisp server and then you use method (1) to retrieve it from the server.
Again, this method only backup the mail message data, nothing else.
People suggested to forward to your ISP (Internet Service Provider). That's just one method. You can forward to any number of places, including another webmail and, my favorite method, to google groups.
The advantage here is you don't have to turn on your machine. It is automatic and able to create high redundancy easily.
I won't divide this into 2 or more methods because it's already a long post and I think this goes beyond the question, but it's worth citing and letting you know.
To configure this all you have to know is the destination e-mail address and where to set it up on your webmail:
Forwarding on Google: http://mail.google.com/support/bin/answer.py?answer=10957
Forwarding on Yahoo: http://help.yahoo.com/tutorials/cg/mail/cg_access5.html
Using Google Groups original article: http://lifehacker.com/248778/use-google-groups-to-back-up-your-gmail-account
(3). Webmail already provides backup options
keywords: offline
This is no backup per say, but Gmail offers offline sync. That will save your messages on your machine, and you can access them going to gmail.com on your browser even without internet access. But while it will save all recent and most important messages (marked with star or some labels) it won't save every message and if anything happens to your account you will mostly have no simple way to read them.
http://gmailblog.blogspot.com/2009/01/new-in-labs-offline-gmail.html
Again I apologize as I know no similar solution on other webmail services.
A final note as a google fan, here is a website made by google employees listing ways to backup your data from other google stuff: http://www.dataliberation.org/