I'm running ubuntu server 10.04 If i change the mac address by adding (in /etc/network/interfaces)
hwaddress ether 12:34:56:78:9A:BC
How reliable is this? Can someone still determine my real mac address?
You'll have to define "someone". If anyone is close enough to your PC to get your MAC address (1 hop), they can probably get it if they really wanted. MAC spoofing is just a software feature. The real MAC is usually stored in read-only memory on the card itself. If the machine is booted into another OS that doesn't have the address spoofed, your real address will be shown.
If you want to change the MAC address at the kernel level, you can use a program called macchanger. It can also randomize the MAC address of a given interface.
Only problem is, if your network depends on DHCP, you'll get a different IP address every time. This can max out the DHCP server's lease cache very quickly.