To install the Legazy app on your Firestick, first enable 'Apps from Unknown Sources' in your Firestick settings under 'My Fire TV' > 'Developer Options.' Then, use the 'Downloader' app available on the Amazon App Store to download and install the Legazy app using its APK URL. Follow the on-screen instructions to complete the installation.