How to suppress "press ESC to exit full-screen mode" in Firefox
 

Since Firefox is cross platform, this is equally Linux and Windows question, but presumably the Linux crowd knows better.

Whenever I go full screen with any kind of video in Firefox I get the "press ESC to exit full-screen mode" warning that plagues my screen for several seconds.

How can I get rid of this?

That isn't Firefox, it's the Adobe Flash player. Google says the answer is in this thread. In short, you have to use a hex editor to zap out the message from the proprietary code. You can also watch the movie with the instructions. Complain to Adobe.