Without diving head first into actual code, the basics of collision detection are this:
You have two objects. For the sake of convenience, lets assume they both have a hitbox that resembles a rectangle: A player, and a wall. Now the player obviously does not look like a rectangle, but that is just the graphics. Behind the scenes little Mario is secretly just a small upright rectangle, that collides with other rectangles.
Checking if two or more of these rectangles collide, is what we call collision detection. We basically check if one rectangle overlaps the other, based on the x/y locations of their respective corners. In the same way, we can also check if a single point is inside a rectangle (convenient for seeing if a rocket collides with a wall), or whether a line intersects with a rectangle (convenient for shooting lasers).
Types of collision detection
The type of collision detection you want to use, depends on how accurate you want it to be. Detecting a point inside a rectangle is obviously easier and quicker than detecting overlapping rectangles. Likewise, if you simply compare the distance between two objects, that is even easier. Most collision detection for 2d games tends to simplify the collision of objects to rectangular shapes, because it is easier.
I'm currently using the bump library for my platforming game. I figured, why try and reinvent the wheel, when others have already tackled this issue way better than I ever could? One of the things bump handles for example, is this collision response, and also tunneling.
Detecting a wall/ceiling/floor
When a player-character collides with a wall, he is usually already inside the wall when the collision is detected. This is why most collision detection corrects the location of the player before the player is drawn. So if my player sprite collides with a wall and stops, what is really happening, is that the rectangle that represents the player intersects with the rectangle that represents the wall. The collision detection then subtracts the distance, so that the player is now next to the wall, instead of inside it. It is important that you first check where the game wants to move the player, and correct the location if there is a collision with a wall, before actually moving the player.
Tunneling is when an object moves so many pixels per frame, that it actually passes right through a collision object, before a collision is even detected. Most collision detection code has a way of dealing with this issue.
Detecting multiple simultaneous collisions
It is important that your collision detection does not just detect one collision, but is able to output a list of all the collisions, and handle them one by one. For example, Mario could collide with both a wall and a coin at the same time. He should collect the coin, and stop when he hits the wall. Those are two collisions that would need to be resolved at the same time.
The most important part however, is collision response. Collision response is what your game does when a collision is detected. For example, what happens when Mario touches a coin? What happens when he touches an enemy? What if he hits a wall? For this purpose it helps if every collision object can be identified by type. Because while Mario can collide with coins, his enemies ignore them completely. That's because enemies ignore any collisions with objects that are pickups/powerups. Not every collision has to stop a game object dead in its tracks. Sometimes you want the object to disappear, or be ignored entirely.
In my game I have water-surface blocks for example. When the player passes through them, the game knows if the player is above or below the water. And thus it switches to swimming or normal movement. For this purpose, it helps if you can also output exactly where the collision occurred. Was the player above or below the y-location of the water? Most collision detection libraries have a way of outputting data about any specific collision.
One of the tricky things about hit detection, is that you don't want to be checking collisions with every game object every frame. Because it can quickly become very demanding. So most collision detection has a way of finding out which objects are eligible for collisions. You might not want to check objects that are off screen.... or maybe you do. You might not want to check collisions with objects that the player isn't even remotely close to, or can't collide with. So basically you want your code to single out a group of objects that are going to be checked.