Se você usa /etc/network/interfaces
para configurar sua interface, existe a opção hwaddress
para definir seu endereço MAC.
Se você usar algum outro mecanismo de configuração, leia sua documentação para ver quais opções ela possui. Por exemplo, o Network Manager tem uma opção especial para falsificação de MAC.
Além disso, existe um script /etc/rc.local
que é executado na inicialização do sistema. Você pode executar o programa que altera o endereço MAC dele.