I downloaded Frets on fire for Linux. With Ubuntu 9.10, that's very easy:
Applications -> Software Center -> Games
and then search for "Frets on Fire".
With the Software Center you can immediately install FoF.
For new songs you can search via google.
Tutorial to add new songs:
1) open console
2) get root: sudo -s
3) move files to the song folder:
mv [source folder of the songs] [/usr/share/games/fretsonfire/data/songs]
4) start game