First of all we have to stop networking. /etc/network/interfaces file and under eth0 (or other network interface) add following line:
hwaddress ether your_new_mac_address
After that you can start networking again.
Example:
sudo /etc/init.d/networking stop
sudo vi /etc/network/interfaces
#now add: hwaddress ether 01:02:03:04:05:06
sudo /etc/init.d/networking start
Jaroslav's Weblog 
this isa really shit post – you should say if this change is permanent or only temporary until next reboot
It’s permanent as long as you /etc/network/interfaces file is not changed