Bom, para usarmos o Bluetooth no Linux, vamos precisar de 3 coisas:

1° Adaptador Bluetooth - Pode ser do notebook ou algum adaptador barato (eu comprei um para teste por 20 reais);
2° bluez e blueman. ( se você tiver outro não precisa ser esses);
3° pySerial instalado para enviar dados via Bluetooth para o Arduino, é o meio mais fácil que achei.


Nessa foto temos adaptador Bluetooth para PC, e o Bluetooth Shield para o Arduino.

Como uso Arch Linux foi assim.

sudo pacman -S bluez
$ sudo pacman -S blueman
$ sudo pacman -S python-pyserial

Com esses softwares e libs instalados podemos sincronizar nosso Bluetooth Shield com o Linux e usar o pySerial para enviar as teclas que queremos assim eliminando o cabo USB.

Como eu gosto de deixar bem manual meu Linux, por segurança eu vou ter que ativar agora meus serviços para funcionar o blueman.

sudo /etc/rc.d/dbus start
$ sudo /etc/rc.dbluetooth start

Obs.: Caso você use alguma distro Debian-like deve estar dentro da pasta /etc/init.d/...

Com o Arduino já conectado com o Bluetooth Shield e ligados em uma fonte de energia, o Bluetooth dele já será visualizado pelo blueman, o meu está com o nome dual.
Repare que eu sincronizei ele e ativei a porta serial nessa conexão ele me deu a porta em /dev/rfcomm0.

Com o endereço do serial via Bluetooth em mãos podemos ir para o pySerial. Abra um terminal para usarmos o miniterm.py (vem instalado com o pyserial que você instalou), use o -h em duvidas.
sudo miniterm.py -p /dev/rfcomm0 -b 9600

Chamamos o programa miniterm.py e definimos a porta /dev/rfcomm0 que é a do Bluetooth e a frequência para 9600, ela já é padrão mas é bom deixar se precisar mudar algo, fica mais fácil pois já vai ser o comando.