How do I Change a MAC address on Debian?

You can change MAC address on Dedian , you have to go this command on terminal:

# ifconfig eth0 hw ether 12:34:56:78:90:aa (Here you get the prefer)

After, UP the interface with ifup or restart the dhcp daemon (networking restart in init.d) and you will have a new MAC address in your NIC.

:)