Ehud was a Benjamite and the phrase translated "left handed man" is a very interesting Hebrew idiom. It literally reads "a man bound/restricted in his right hand." The same phrase is used in Judges 20:16 to describe 700 slingers (also of the tribe of Benjamin). These two verses are the only places where this idiom is used.
Judges 20:16 Among all this people there were seven hundred chosen men bound in the right hand; every one could sling stones at an hair breadth, and not miss. [KJV with the left handed idiom shown more literally]
There is another phrase used much more frequently to describe being left handed or turning to the left (sim'el). It appears 54 times in the Old Testament (e.g. Genesis 13:9; 2 Samuel 14:19).
Genesis 13:9 [to] the right, then I will go to the left. (NASB)
2 Samuel 14:19 one can turn to the right or to the left from anything. (NASB)
Noting that both instances of the "bound in the right hand" idiom refer to Benjamites, the translators' notes on the NET state:
Perhaps the Benjaminites purposely trained several of their young men to be left-handed warriors by restricting the use of the right hand from an early age so the left hand would become dominant. Left-handed men would have a distinct military advantage, especially when attacking city gates. See B. Halpern, “The Assassination of Eglon: The First Locked-Room Murder Mystery,” BRev 4 (1988): 35.
1 Chronicles 12:2 also mentions a squad of ambidextrous soldiers who were also Benjamites. David's general Joab is also shown to be either left handed or ambidextrous in 2 Samuel 20:8-10. He grabs his opponents beard with his right hand while holding a sword in his left. The opponent takes no heed of the sword in his left and is undefended when Joab strikes. (See also the Iliad, 21.161-68, where Asteropaios, being ambidextrous, throws two spears at once at Achilles.)
When Ehud approached the room to see Eglon, he would have been inspected by the guards. As being right handed was more common then (just as it is now), they would have searched his left side for a concealed weapon more carefully than the right. A right handed person draws a long blade from the left side. Apparently, upon seeing the left side was clear, they didn't search the right for hidden weapons. After all, it was unlikely that he could draw and use a blade from that side.
Aside
The military advantage to being left handed are such as the enemy expects to be fighting a right handed man. The lefty has the element of surprise which even for a few seconds can determine the outcome. This holds only for individual combat. Units fighting together would want all to be using the same hand. Then, if you have a whole unit of lefties against a unit of righties, you have the left advantages again. They are trained to fight righties (and are attacking the unshielded side), while the righties have to rethink and mirror every offensive move they make while trying to stay alive.
In the Lincoln Cathedral, the spiral staircases are wrong handed and were defended by men from a Scottish clan almost exclusively left handed. The reversed direction caused invaders to be holding their weapons and shields on the wrongs sides as they tried to climb, but the defenders would fight unhindered.