There have been tools around for a long time that will allow you to change your mac address.  The most famous of which probably being SMAC.  Most (if not all) of them are proprietary programs that cost money.  If you've ever bought one of these programs, I've got bad news for you, you paid money for a program that changes a single registry entry.  That's right, you've been had.

To get technical, the registry entry in question is HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Class\{4D36E972-E325-11CE-BFC1-08002Be10318\<XXXX>\Ndi\params\NetworkAddress where <XXXX> is the id of the NIC you're working with.  If the value of that key is set, Windows will use that value as the MAC address of the NIC, otherwise it uses the hardcoded MAC address on the NIC itself.  But that's the hard way of doing it.  Now there is a free program that lets you do this and gives you some pretty nice options to tweak it to your liking. 

Technitium MAC Address Changer is a free tool that lets you choose from a list of manufacturers' MAC addresses, use a custom MAC, use a random MAC, use a random MAC from a certain vendor, restart the card and apply the changes instantly, save and load presets, and a load of other options.  If you need a Windows program to manage your MAC address, and any security professional will need this at some point, TMAC is your best choice.

Now, on to how to do it in Linux.  Just open up a terminal and run the following as root:

 ifconfig eth0 down
 ifconfig eth0 hw ether XX:XX:XX:XX:XX:XX
 ifconfig eth0 up

Where the X's are the hex for the mac address.  Of course, if you don't want to change eth0, you can replace that with ethX or athX or whatever your interface is called.  Or you can do it the easy way and use a program called macchanger which is readily available in most package management schemes.  macchanger's website has some great examples of how to use it.