According to the Angler page on the official wiki, this NPC can be found sleeping in the sand of an Ocean biome. Are there any other specific requirements to find him, i.e. hard mode or the like? I searched both ocean biomes in my world, and I didn't run into this new character. Is encountering him, like most other things in this game, simply random?
Hardmode is not required. His appearance is random, and (as of 5/12/2014) there is a bug where if the beach part of the ocean biome is too small, he can appear out on the water's surface instead.
No additional prerequisites have been found. You do not even need an open house slot before he'll appear; mine appeared when all my housing was full.