To Pen8bits: sorry, missed that. Now fixed, available at the same location.
As for the other questions. As it was was already guessed, the patched emulator replaces original patterns with modified ones when rendering. If the replacement pattern is not found, the emulator renders the original one. Both the original and the replacement patterns are stored in a skin.png file. This file has no link to a ROM, so this indeed should work for basic level hacks, if the tiles themselves were not touched. And of course you can draw your own replacement patterns if you don't like those in the skin.png. Another consequence of not being tied to a ROM is that graphics can be changed for any ROM by redrawing original patterns in a skin.png. But if you dare do this, you should be aware of some important limitations. I'll write them down, if a need arises.
Concerning the request to make a patch for Castlevania 2, to my taste, it is good enough as it is. Actually I can't think of any other NES game that requires such a patching. The reason behind making this patch for Castlevania lies in how I got acquainted with the series. The first game I saw was Vampire Killer for the MSX 2. It was early 1988 in the computer classroom of our school. The NES version fell into my hands much later, in the beginning of the ninetees after the fall of the iron curtain, when parents bought as a Dendy (russian NES clone). I was shocked by the smoothness of the scrolling (both MSX and 286 PC had problems with it), but disliked the downgrade in the graphics. Ever since I dreamed of upgrading the NES version tiles to at least the MSX level. This would've never happened because I can't draw.
But KONAMI has redrawn the tiles for the mobile phone release of Castlevania. Unfortunately they've split the release in three parts, 6 stages each. The first one is widely available, but I can't find the second and the third anywhere. If you happen to stumble upon them, please let me know. Later KONAMI has released the complete edition for the Japanese phones. But they have redrawn the enemies, making them worse (to my liking). Anyway I would really like to get that version as well, to grab the original tiles for the font, intro and ending. I have the complete edition for Chinese phones, but the font there is hyeroglyphic, and the intro and the ending are redrawn once again for the worse.