Sometimes during the AmiDeb install, fs-uae fails to install.

Once you have the system booted from having done the install, go to the Utilities Menu, and then choose option 7 (Start Command Shell).

Then issue this command: sudo apt-get install fs-uae

Answer yes to any questions.