Follow these 3 links, and do what they say:
http://code.google.com/p/atv-bootloader/wiki/BootEFIExtraction
http://code.google.com/p/atv-bootloader/wiki/InstallParted
http://code.google.com/p/atv-bootloader/wiki/InstallHFSTools

(If you need to do a backup, look here: http://code.google.com/p/atv-bootloader/wiki/ATVBackup )

Be aware that ”/dev/sdb” isn't always your usb-stick. (You could potentially erase your hard-drive)
Use “parted -s /dev/sdb print” to verify if it's the correct stick.

# Zero the initial sectors
sudo dd if=/dev/zero of=/dev/sdb bs=4096 count=1M

# Sync the system disk partition tables
sudo partprobe /dev/sdb

# Create the GPT format
sudo parted -s /dev/sdb mklabel gpt

# Create just a recovery partition
sudo parted -s /dev/sdb mkpart primary HFS 40s 69671s
sudo parted -s /dev/sdb set 1 atvrecv on

# Sync the system disk partition tables
sudo partprobe /dev/sdb

# Verify that it looks fine and the atvrecv flag is set sudo parted -s /dev/sdb unit s print
—— Model: SanDisk Cruzer Micro (scsi)
Disk /dev/sdb: 501759s
Sector size (logical/physical): 512B/512B
Partition Table: gpt

Number Start End Size File system Name Flags
1 40s 69671s 69632s primary atvrecv
——

# Format it
sudo mkfs.hfsplus -v Recovery /dev/sdb1

# Mount it
mkdir penboot
sudo mount /dev/sdb1 penboot/

# Download atv-bootloader (recovery.tar.gz) and install it
wget http://atv-bootloader.googlecode.com/files/recovery-0.6.tar.gz sudo tar -xzf recovery-0.6.tar.gz
nano penboot/com.apple.Boot.plist, and change atv-boot=auto to atv-boot=none
sudo cp -arp recovery/* penboot/

# Copy the bootloader gzip to penboot/ for later use
sudo cp recovery-0.6.tar.gz penboot/

# Remember to copy boot.efi to penboot/
sudo cp -ap boot.efi penboot/

# Download netboot image
http://us.archive.ubuntu.com/ubuntu/dists/karmic/main/installer-i386/current/images/netboot/netboot.tar.gz

# Unpack files
tar -xzf netboot.tar.gz

Now copy just “linux” and “initrd.gz” to the atv-bootloader USB flash drive
cp ubuntu-installer/i386/linux penboot/
cp ubuntu-installer/i386/initrd.gz penboot/

# Unmount the disk
sudo umount penboot

Connect your usb-hub to the AppleTV, and plug-in a keyboard and your usb-stick.
Press and hold “minus+menu” on your AppleTV remote to reboot into the bootloader.
If that for some reason don't work, you can cut the power to your AppleTV,
and let it start up with usb-stick in.

When it's done booting, you will see the ip that it got from dhcp on your screen.

Connect to that ip using telnet, and use the login/password “root”.
telnet
open your.ip.adress

From your telnet window:

On your AppleTV ”/dev/sda” is the internal hard-drive, so here it's no harm to copy/paste the lines.

# zero /dev/sda first or pre-existing guid will not change
dd if=/dev/zero of=/dev/sda bs=4096 count=1M

# create initial gpt structures
parted -s /dev/sda mklabel gpt

# find max size of disk (see Disk /dev/sda: XXXGB from listing)
parted -s /dev/sda print

In this example 160GB is used as the ending point.
Swap partition is fine at about 1GB.

# create a 25MB “EFI” partition (starting at sector 40 is important)
parted -s /dev/sda mkpart primary fat32 40s 25M
parted -s /dev/sda set 1 boot on

# create a 25MB “Recovery” partition
parted -s /dev/sda mkpart primary HFS 25M 50M
parted -s /dev/sda set 2 atvrecv on

# create a 25MB “OSBoot” partition
parted -s /dev/sda mkpart primary HFS 50M 75M

#create the linux root partition
parted -s /dev/sda mkpart primary ext3 75M 159.0GB

#create the linux swap partition
parted -s /dev/sda mkpart primary linux-swap 159.0GB 160.0GB

# sync the system partition tables
partprobe /dev/sda

# verify the partitions
parted -s /dev/sda print

# you should see something similar (note boot and atvrecv flags)
Model: IC25N020 ATDA04-0 (scsi)
Disk /dev/sda: 20.0GB
Sector size (logical/physical): 512B/512B
Partition Table: gpt

Number Start End Size File system Name Flags
1 20.5kB 25.0MB 25.0MB primary boot
2 25.0MB 50.0MB 25.0MB primary atvrecv
3 50.0MB 75.0MB 25.0MB primary
4 75.0MB 18.9GB 18.8GB primary
5 18.9GB 20.0GB 1104MB primary

# format the partitions We will let the netboot install setup swap.
mkfs.msdos -F 32 -n EFI /dev/sda1
mkfs.hfsplus -v Recovery /dev/sda2
mkfs.hfsplus -v OSBoot /dev/sda3
mkfs.ext3 -b 4096 -L Linux /dev/sda4
sync

#Copy over the bootloader
mkdir /tmp/a1
mount /dev/sdb1 /tmp/a1
mkdir /tmp/a2
cp /tmp/a2/recovery-0.6.tar.gz /tmp/a2/
cd /tmp/a2/
tar -xzf recovery-0.6.tar.gz

# Make some mount points
mkdir /mnt/osboot /mnt/recovery

# Mount the partitions
fsck.hfsplus /dev/sda2
mount /dev/sda2 /mnt/recovery
fsck.hfsplus /dev/sda3
mount /dev/sda3 /mnt/osboot

# Copy atv-bootloader to internal drive
cp -arp /tmp/a2/recovery/* /mnt/osboot/
cp -arp /tmp/a2/recovery/* /mnt/recovery/

# Copy boot.efi from usb-stick
cp -ap /tmp/a1/boot.efi /mnt/osboot
cp -ap /tmp/a1/boot.efi /mnt/recovery
umount /mnt/osboot
umount /mnt/recovery

#Bootstrap into netboot installer
kexec –load /tmp/a1/linux –initrd=/tmp/a1/initrd.gz –command-line=“vga=normal vesa video=vesafb”
kexec -e

You should now see the familiar red/blue install screen on your TV.
Proceed with the keyboard you connected earlier, the telnet session is closed.

Follow the steps of the installer. When asked for username, do NOT use “xbmc”, also remember to use /dev/sda4
formated as ext3 for ”/”, and /dev/sda5 for swap. Grub path doesn't matter, just use /dev/sda4
When you come the “Software selection” window, choose only “Basic Ubuntu server” and “OpenSSH server”. Installer
does it's thing… When it's done, repeat “Step 4”, and proceed.

In the telnet session again:
mkdir /mnt/ubuntu
mount /dev/sda4
cd /mnt/dev/sda4/boot/
ls -la

Write down the version on your vmlinuz and initrd files.
It should look something like this:
vmlinuz-2.6.31-17-generic
initrd.img-2.6.31-17-generic

cd grub
rm grub.cfg
nano menu.lst

Edit your menu.lst to something like this:

default 0 
timeout 3 
title linux 
root (hd0,4) 
kernel /boot/vmlinuz-2.6.XX-XX-generic root=/dev/sda4 ro 
initrd /boot/initrd.img-2.6.XX-XX-generic 
boot 

Change XX with the version you wrote down earlier.
Make a copy of your menu.lst, It's broken on every grub/kernel update,
so you will need to repeat these if that happends.

cd /
umount
reboot

You should now have rebooted your ATV into Ubuntu.
Don't worry if you can't see any login-screen on your TV,
we will fix that later.

# SSH into your box
ssh yourusername@appletv.ip

# Add XBMC PPA
sudo apt-add-repository ppa:team-xbmc-svn

# Install needed software
sudo apt-get update
sudo apt-get install xbmc envyng envyng-core x11-xserver-utils xinit

# Adding xbmc user
sudo adduser xbmc –gecos XBMC
sudo usermod –group audio,video,netdev,fuse,plugdev xbmc

# Install gfx drivers
sudo envyng -t

Choose the 190 driver, that have worked good for me at least.
When Envy is done, choose reboot, then ssh in with your xbmc user when it's up.

# Change tty1
sudo nano /etc/init/tty1.conf

Change this line:
exec /sbin/getty 38400 tty1

To this:
exec /bin/login -f xbmc </dev/tty1 > /dev/tty1 2>&1

# Create bash_profile
nano ~/.bash_profile

Fill with this:
case “`tty`” in
/dev/tty1) clear && startx &>/dev/null;;
esac

# Create xsession
nano ~/.xsession

Fill with this:
exec xbmc –standalone

That's it. This is how I did it at least, and it works fine for me.