Each zone has an associated level of fishing that defines the difficulty of catching a fish. The higher your fishing skill is in relation to the level that a zone requires, the easier it will be to catch fish. If your skill is below the zone's requirement, you will catch junk items rather than fish. As of Patch 3.1, there is no longer a minimum skill level required to fish in a zone, and the former 100% catch rate (no get-aways) level is now the 100% fish (no junk) level.
Silmyr Lake was raised in to the highest fishing tier in patch 2.4. With the addition of the Wrath of the Lich King expansion, Northrend now has many zones which exceed this tier.
The lowest fishing skill, trained as an apprentice with no experience, is 1. Training is required in order to use a fishing pole to fish, so the lowest skill required is 1.
Note that the highest unaided fishing skill that a character can have is 450. Ensuring a catch in the upper tiers (up to 575) requires gear with bonuses to fishing skill. The bonuses to fishing skill from equipped items stack.
Fishing skill above the skill required for 100% catch rate is wasted, so you do not always need to equip a lure. For example, fishing in tier 1, the +25 fishing skill [Shiny Bauble] lure would be helpful when you are first starting out, but once you've caught around 30 fish, it would be superfluous to use a lure in the starting area.