For a domain with one of the main extensions (.com, .net, and .org) you can expect to pay from $5 up to $35 per year. Verisign, the oldest and best-known domain registry, is also the most expensive.
A domain name alone is just an address. If you want to get mail there, you need to get mail services. Some companies offer both registry and hosting services — almost always web and mail hosting — and will offer discount pricing if you use them to both register and host your domain.
You should start your hunt by checking out the registries you're thinking about using at RegSelect, an independent guide to domain registrars. For web hosting companies, you can see what people have to say about them at WebHostingTalk Forum, a popular web host discussion site.
When shopping for a site that will host "MineAllMineHaHaHa.com," you should look for ones that offer easy Simple Mail Transport Protocol (SMTP) and Post Office Protocol (POP) support, the two essential mail services. You may also want to use a provider that will let you use web mail, a service where you can read your mail from any web browser.
This last feature is especially important if your primary Internet provider doesn't let you access SMTP mail services. This used to be extremely uncommon, but now many major ISPs like BellSouth.net won't let you use SMTP mail services, which are used to send mail, unless they're providing it for you.
ISPs are doing this in an attempt to cut down on spam, but at the same time, it's also making having a mail domain for your own legal use harder. If your ISP follows this policy, there's probably a way around it, but be ready to spend some time with their technical support people getting it worked out.
Mail storage is also a consideration. The forthcoming Google Mail, GMail, will offer you an amazing 1 gigabyte of storage, but it's more common to find services that offer only 10, or even 5, megabytes of mail space. That may not be a problem if all you ever do is send and receive text messages, but if you're not good about cleaning out your inbox or you're getting megapixel photos of your grandkids, you'll want as much room in your mailbox as you can get.
In these days when every other piece of mail is spam, and every third piece that comes along has a virus, you can also shop around for hosting companies that offer spam and virus protection. These are premium services, though, and you can expect to pay $10 to $60 more a year for them from most sites.
If you have a domain name that you just love, but it's long gone, consider using an alternative top level domain (TLD) name such as .info, .name (specifically for people who want their name for their domain), or .biz instead of the more common .com and .net TLDs. Names that have long been taken in their .com forms are often available in these other formats.
Which way is best? Well, for ease of use and cost, it's hard to beat the big name, free online mail sites like Hotmail and Yahoo. Their web mail interfaces also feature the advantage of not being blocked by some ISPs. But, if you really want an address that isn't going to change, you can't beat a domain name of your own.