Binding of Isaac has an achievement for "A Gift From Krampus". The hint says it's in Satan's room, but I don't know where that is.
Amongst other factors, beating the boss without losing health increases your chance of seeing satan's room, occasionally satan will not be there and you can instead fight Krampus. He fights similar to the fallen.
The Binding of Isaac is a tricky game, and this achievement is made worse by its randomness.
As others have said, Krampus can be found in Satan's Room, which appears after a boss has been defeated, usually if you did well (took very little damage) on a level. The first few levels of any Binding of Isaac game are generally not that hard.
Krampus is a boss-like enemy with two major moves. One move fires 4 laser beams in a cross pattern. Before he does this move, he looks like he might sneeze. The other move fires a set of red shots in your current direction. He winds up with this move by puffing out his cheeks. As long as you keep moving, and stay out of the cardinal directions when the laser move is charging, you'll be fine.
General Isaac Strategy
You'll start with a key and a bomb, in a room that explains the controls. You can find keys, bombs, coins, hearts, and other items in the various rooms on each floor. I always explore the entire level before attempting to fight the boss.
If you encounter an item, and aren't sure how to use it or if you want to buy it, consult this list on the Isaac Wikia. Many items are tricky or not fully explained in the game. Items that activate with Space need time to recharge - depending on the item, you'll have to clear a number of rooms in order to recharge it. Try to save these for the bosses if they're particularly useful.
There will be one room with a "golden" door in it. That room will always contain an item. On the first level, it's unlocked, but on other levels it will be locked and you'll need a key. Always prioritize these rooms if you can.
The only other rooms that are locked are the shops. Don't bother unlocking the shop unless you have a good number of keys (say, 3 or 4 or more) and/or a good number of coins (ideally 5-10 or more). Otherwise, you'll waste the key to see the shop's inventory, which you can't afford.
Bombs can be used offensively, but there's usually a hidden room on each level that's a better trade. Finding it without certain items (like the X-Ray Specs) can be hard, but it's usually the empty space which is most surrounded by other rooms.
There are other objects and rooms you might encounter, (like the arcade, or blood machines/slot machines) but they're fairly rare in the first few levels, which is really where you want to focus for this achievement.
There's also occasionally a door that has crossed swords on it, this is the challenge room. For the purposes of this achievement, just ignore this - it's usually got a chest with a few items in it, but you'll have to then fight waves of enemies.
After fighting the boss of a level, you'll have the option to leave the level via a trap door. When the trap door appears, if you qualified for the Satan's Room on that level, it will open a new door in one of the walls.
If you make it past the first couple of levels and don't encounter a Satan's Room, try starting over. Sometimes you'll get a really powerful item early that will make everything easier. In general though, learn the attack patterns of the enemies, and stay on the move. You'll quickly get the hang of it.
I got this in 15 minutes in my first Devil room, but apparently the odds of that happening are abysmally low. I don't have hard numbers on the probability of Krampus spawning, and I can't find any references of anyone who has crunched the numbers. The community consensus seems to be that using Cain causes him to spawn more frequently. I would suggest playing only the first few floors of the game, to minimize the headaches of playing the lower floors for far less gain than the early floors.
On the other hand, some of the optional bosses only spawn after the game has been cleared a number of times, (For instance, the Horsemen only spawn after Mom's been defeated) so if you've run the first few levels already and gotten devil rooms without seeing him, it might make sense to try clearing the game once or twice to see if that makes a difference. For reference, I had cleared the Womb levels before, but I had not yet gotten to Sheol.
If you're having trouble avoiding damage, try slowing the game down. I throttle my CPU on some of the lower levels to make the game a bit easier, personally. You'll have way more time to dodge and react to enemy fire this way.
I found him in satan's room right after beating monstro or whatever the name is..(bought it like half an hour ago lol) No achievement though. Glitched?
Unfortunately, there is no way of telling when Krampus will spawn. However it is more likely with Cain as he has the Lucky Foot, which increases the chance of Devil Rooms, rare treasures, etc.
Also to fight Krampus you have to be of some skill (keep in mind he is harder than The Fallen) but if you can beat the Fallen easily, then you should be able to kill Krampus. The attacks of the two bosses are almost the same and he will always drop the same item. He has the same amount of health as your average Chub and he is a very unpredictable boss. You can find more information on this boss here: http://bindingofisaac.wikia.com/wiki/Krampus