You should be able to go “really full screen” with GraphicsDevice.setFullScreenWindow (window). However, due to bugs in the most popular Java runtimes, this may not work on systems running certain “broken” versions in the 1.6 = Java 6 series. I haven't tested this thoroughly, so it may be that the patch hasn't propagated out to the general populace, yet.
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7057287
Background/Theory
OK, so here goes for too much information, and not enough help… Here's a bit of why this didn't work right…
There is no Linux Desktop
Linux-based operating systems on PC-type machines, as well as other Unices (with a partial exception for MacOSX), normally use the X Window System (aka X11). Under X, you have an X Server (usually, something kinda like a “video driver”) and clients that connect to it, more often than not, from the same machine (loopback).
The layout and placement of windows is controlled by a special client program, called the Window Manager. It's responsible for decorating the windows (e.g. drawing title bars or resize handles) and positioning them.
Your program would be an X client. It can request — but not demand — placement on the screen at a certain position, or a certain size. Various Window Managers are more (or less) prone to giving you what you want.
Except, most desktops play nicely (sometimes)
Now, by far, most Linux desktops use the Gnome Desktop, with a strong second place for the K Desktop, and a few others are in fairly wide use. What's “nice” is that both of these desktop environments (as well as some others, like XFCE for low-end PC's) conform to the FreeDesktop.org Window Manager Hints standards.
(Super-over-simplification:) Typically, there will be Panels on one or more edges of the screen. Usually, there's just one, across the top, but there are many variations. These Panel areas are not considered “part of the screen,” so the Window Manager tells your application, “no, that's outside of the area in which you're allowed to play; this screen is not 1920×1080, it's only 1890×1080.” Of course, that could be totally different arrangement than what you'd anticipated when you wrote your app, and you might be on my netbook with a physical screen of 800×480 pretending to be only 780×480.
For 99% of apps, that's great. Windows don't get in the way of the Panels, so you can always reach the Panel for critical controls, like hitting Mute or switching to another program or something.
These “hints” allow you to request that your top-level windows get treated specially. For example, you can request that you get no title bar — or a reduced, “palette” type title bar; you can request to be skipped on the window list or task bar or activities overview or whatever other interface might be used to show the active windows; or, you can request to go really full-screen, and push everything else out of the way, even panels.
The spec is here: http://standards.freedesktop.org/wm-spec/wm-spec-latest.html
And the Fail:
Basically, the window manager hints specification wasn't being followed correctly by Sun/Oracle (or Red Hat, who copied off Sun/Oracle, or probably IBM, because they probably did the same, but I don't see anybody complaining about them)…
Although, I do see some griping back and forth about whether it's a bug (specifically) with the K Desktop Environment's window manager (KWin), as apparently this bug only shows up in K, and not in Gnome, XFCE, and friends.
Work-Around
Aside from patching your Java runtimes (and/or your customers'), the only real fix would be to use the platform-specific Java libraries (perhaps grab the underlying AWT objects using reflection… eww…) and set the proper window hints, yourself.
Yes, that's gross…
