There is more than one way to change the MAC address of a network device on Linux. One possibility is to use the ip command, but here I will show how this can be done using the macchanger command as it is a more intuitive tool for this task. On Ubuntu/Debian, you can install it by opening a terminal and running:

sudo apt-get install macchanger

Before changing the MAC address of an interface, you must first bring it down:

sudo ifconfig <interface> down

For instance, if the interface whose MAC address you wish to change is eth0, run:

sudo ifconfig eth0 down

Now you can change the MAC address of your interface with the following command:

sudo macchanger -m <new-mac-address> <interface>

where the <new-mac-address> must have the format XX:XX:XX:XX:XX:XX, with each 'X' being a hexadecimal digit (e.g. a1:b2:c3:d4:e5:f6). The output of the command above will show three MAC addresses: the permanent one (fixed by the vendor), the current one (before changing it) and the new one you chose. This what I got after setting the MAC address of my eth0 interface to aa:bb:cc:dd:ee:ff:

Permanent MAC: f0:4d:a2:95:77:31 (Dell Inc.)
Current   MAC: f0:4d:a2:95:77:31 (Dell Inc.)
New       MAC: aa:bb:cc:dd:ee:ff (unknown)

To restore the interface's MAC address to the original value, run:

sudo macchanger -p <interface>

A MAC address is a 6 octets (48 bits) long identifier which is assigned to a device when it is manufactured. It is (usually) a globally unique value. The first 3 octets (24 bits) identify an organization (e.g. Intel Corporation, Cisco Systems, Netgear Inc. etc.; this organization is commonly the device vendor) and correspond to an Organizationally Unique Identifier (OUI). Vendors must purchase OUI's from the IEEE registration authority. You can get a list of OUIs and the organizations they belong to with:

sudo macchanger -l

When a device is manufactured, the last 3 octets (24 bits) of its MAC address are chosen by the vendor.

To assign a random MAC address to your interface while keeping the OUI unchanged (in other words, a MAC address from the same vendor), run:

sudo macchanger -e <interface>

To assign a random MAC address from any known vendor to your interface, run:

sudo macchanger -a <interface>

Finally, to assign a completely random MAC address to your interface (this will very likely generate a MAC address with an invalid OUI), run:

sudo macchanger -r <interface>

MAC spoofing

If you set the MAC address of your interface to the MAC address of some other device in your network, you will be de facto impersonating it. This is a form of attack called MAC spoofing. As a simple test, I have changed the MAC address of my laptop to the MAC address of my mobile phone and then connected to my wireless router (the phone was already connected). Unsurprisingly, the Internet on my phone stopped working and only started working again after I disconnected my laptop from the wireless router and reconnected the phone. This is a classical case of a denial-of-service attack (if I kept on reconnecting my laptop to the router, my phone would be permanently deprived of Internet access).

In the attack I simulated, the denial-of-service happens because there are encryption parameters which must be in sync between a connected device and the wireless access point (WAP). By connecting my laptop to the WAP using the same MAC address as my phone, I have effectively made my phone and the WAP become out of sync with respect to these parameters and therefore incommunicable.

Bonus: The Coca Cola Company

I was surprised to find out that The Coca Cola Company has its own OUI. To see it, run:

sudo macchanger -l | grep Coca

This is what you should see:

14691 - fc:d4:f2 - The Coca Cola Company

Needless to say, such a weird fact did not go unnoticed on Slashdot.