I'll be focusing first on the "How does anyone find that?" part of your question, but that will lead us to the "how did they get there" portion too:
There are a few ways.
Some things will just happen by random chance. I have come across glitches in some games where I've fallen through the floor, for example. Often these funny mistakes get spread around, because they are interesting and unusual. With millions of players, playing for cumulatively 10's or 100's of millions of hours of game time, you'd be surprised at the "glitch" conditions which can be generated purely by accident. Some of these things will be spread around, by word of mouth or particularly in the internet age, by videos etc. on social networks or on YouTube.
Programming knowledge leading to discoveries
Second, if you have ever tried to program games, or even if you've just tried any kind of coding in general, you may be able to, when you play a game, think about how it's likely to have been coded. For example, I have only ever coded one thing which somebody might charitably call a game - as part of a university project. That game had collision detection, admittedly only in 2D and really only for the player character, so it would have been much simpler than the implementation in Mario, but there are still some things we can learn.
Collision detection is a system with code which figures out if the character you are controlling (or indeed, any other object, character etc.) has collided with an object, the floor, another character, etc. - typically, for the player character, it will work something like this:
For each frame:
- Move the character where you're telling it to move (calculate a new position based on movement speed and direction)
- Check if any part of your character (or maybe just a subset of points related to the character's limbs to make it simpler, or sometimes just one point relating to your character's position, depending on the nature of the game, player models, etc.) is inside of another object (or character etc.) - if this is the case: move the character back so they are just touching the wall/character/object, and possibly perform some action - if Mario has run into a wall fast enough, he might "bonk" off of it and say "ow!". More generally, not just for collision detection, the process is: Change some state about the game (player position, move speed, etc.), check the new state for anything important, if anything important has happened or there are problems with the new state (such as the character being inside a wall), do something about it (resetting values, having a collision "bonk" and repositioning, updating the player's score, killing the player, etc.).
Having coded a very basic implementation of this myself, I ran into a problem: My player character could speed up as the game progressed. If he went fast enough, I could (potentially) run into a problem where on one frame he is to the left of a wall moving rightwards, I would calculate his new position based on direction and speed, check to see if his position was intersecting a wall or object, but find that because of his high speed, he has actually passed entirely through the wall or object so that he is fully on the right side of the wall, without intersecting on the next frame, and therefore my collision detection code would say "Nope! Everything OK! Don't need to do anything here!". One of the key things to realise here is that speed, position etc. are calculated and checked in discrete increments - in most modern games this will be 60 times per second as this is the frame rate the game runs at - and as the travel speed increases, as the character travels further between each frame, the distance between each check that occurs increases.
There are ways to code around this, but it was what's called an "edge case" - the character would have to be going very fast for this to happen, and it's extra work to code in this more robust way - besides, I worked it out and the character could never actually get up to a speed fast enough to cause this to happen.
But what if I was wrong about that? What if there's some edge case or just outright mistake in the code which calculates the character speed? What if I've limited the speed a character can run at, but I've got something which increases your speed when you do a certain kind of jump? Like a long jump? Even if only temporarily? Say I've coded it so that when you do a long jump, you're travelling faster than the max run speed while you're jumping, but you very quickly slow back down again when you hit the ground, say within 2-3 frames (to make the animation look smooth, for example). What if, then, the player realised that with extremely precise timing they could chain long jumps together, and have it so that the second (and third and nth) long jumps increased the speed even further?
Well OK. I've realised this and caught it, and coded in a hard speed limit for the character. The character can now only move forwards at a maximum of 20 units per second (this is an arbitrary number but you get the idea). What I've failed to account for though is that under certain circumstances such as standing on a steep staircase, the player can perform a long jump but it'll actually move them backwards! I've put a forwards speed limit in but not a backwards one, and now the character can do a backwards long jump over and over again, provided they are standing facing down a steep enough slope, build up extreme speed, and that with this extreme speed they can end up in the situation I mentioned where they clip straight through a wall very quickly (essentially they would be "inside the wall" between frames and position checks), and the collision detection code which is meant to stop your character passing through that wall doesn't detect any problems.
So what you can take from this is two things:
- Glitches are often a result of edge cases which the programmers thought were either impossible (mistakenly) or that would be so rare that it wasn't worth the extra effort to code around. They might also be a result of multiple edge cases for different systems in the game (movement and collision detection in this case) interacting with each other.
- If you understand how at least some aspects of game coding in general work then you may be able to make guesses about how you can break the game - in this case, knowing how collision detection is generally implemented, you might already have realised that a) speed can break it, and b) there's a speed limit for Mario going forwards, but when you see a backwards jump which seems unusual, you may think "Ah, I wonder if they remembered to put a speed limit in for that?", test it out, and it turns out that no, they didn't, and voila, you can break the game.
Deconstructing the actual game code
This next method is a step further from the above: If you can manage to get the code onto a PC (which could be done all sorts of ways, from just reading game discs directly, to more involved methods like connecting to console expansion ports, sometimes by the creation of additional specialist hardware; soldering additional wires to console main boards, etc.) then you can decompile the code. Source code for any kind of program typically looks something like this:
If ButtonPressed.MoveForward = true; Has the player pressed the button to move forward?
PlayerSpeed += PlayerAccel; Increase the player's speed by PlayerAccel figure
If Player.Speed > PlayerSpeedMax; Check player speed
Player.Speed = 20; Reset player speed
Now this is a very simplistic example, not from a real programming language, but the point is that you can look at it and fairly easily (especially if you know the particular language) work out exactly what's going on. This is how the original game programmers make the game. If you had access to this code you could very easily look for things that are not coded robustly and exploit them. Unfortunately the code you get from dumping game files is not this - the code is compiled which means that some software takes it from easily-human-readable codes and converts it into code which the computer chip can execute very quickly. It looks something more like this:
(Note this is not the same code, this is a random example - also this is x86 code for a PC, and not Nintendo native code, which would look different, but be more or less as difficult to read)
As you can see it is NOT easy to read, there are no variable names or comments to tell you what's happening. There are additions, subtractions, moving data from one memory location to another, conditional jumps to new places in the code etc. - it is not easily-human-readable but that's fine, because the computer only processes the numbers and outputs the results, it doesn't need to know whether a figure relates to the player's speed in order to perform the necessary calculation. Unfortunately, this is what you get back when you decompile the code from a game. Now importantly, with the use of emulators and tools, you can look at the values of any one of these variables at a point in time.
So it is possible to do things like look at the variable held in a particular memory location and watch how it changes over time. If you were looking for a "Player Speed" variable, you could put a watch on 20 different variables, play the game a bit, move around and see which variable changes as you'd expect with player movement (increasing as you run faster). Another thing which can help is that sometimes messages which come up in game, like "I'm sorry Mario, the Princess is in another castle" may be in the code in plain text, so they can give you clues as to which variables make certain things happen. Alternatively you could make changes to some value (change a 1 to a 2) and see how that affects what happens in the game - though often this is more likely to just break a game and make it crash.
Once you've figured out which variable it is you've been looking for, you can use decompilation software to start reconstructing something like the original code, (note you can never reconstruct a perfect version as some information is lost - but you can make educated guesses) and name that variable as something like Player.Speed instead of something unreadable. You can do this again and again and again until you have something which more resembles the original game source code, piecing it all back together as you go. It's a long and arduous process, and the result will be messy, and the variables won't have the original names, and there will be no comments on the code (except any which you add to help you keep track) but again, it doesn't need to be perfect to still help you figure out how you can break the game.
In fact, people have done this exact thing, with Mario 64, and almost certainly with other games too.
Source code leaks
Occasionally, although very rarely, the actual original source code, that is, the code which the programmers wrote when the game was originally created, in easily-human-readable code, with comments and helpful variable names etc., gets leaked to the public. In some cases, a developer will freely release the code - Id Software did this with a number of its older games including Quake 3, but it's something Nintendo, to my knowledge, have never done. It would need to be released by somebody working for the company, or somebody who has hacked into the company's servers etc.
However, the (I think partially incomplete?) source code for Mario 64, Ocarina of Time and Majora's mask did finally leak this summer, back in June, which was huge news at the time.
Anyway, as explained above, if you can see the game's code (either by seeing the actual original code or reconstructing some semblance of it) then you can find glitches more easily.
I realise I've been talking about Mario here but the general processes described above will work for any game... it can be a lot of effort for a complex game - it may take thousands of hours to decompile and reconstruct - but these days with vibrant speedrunning communities etc. more people have the incentive to do it. Also bear in mind that often in order to break certain aspects of a game you might only need to deconstruct a small percentage of the whole game's code. If you're only trying to break movement, then you don't have to reconstruct the code for the game's item-handling system, for example.
So generally we can walk away with the following knowledge:
- Programmers make mistakes and miss things - programming for every possible situation is really hard and rarely worth the effort.
- Programmers are lazy - or to put it more positively, they make efficiency choices about programming around edge cases - if something will happen very rarely, like a player would have to do something with very very precise timing, multiple times for something to happen, and it's very unlikely to ever happen by chance for more than one in 100,000 players, is it really worth spending 10's or 100's hours changing all of your code in complex ways to make sure that can't happen, or is it not really worth it?
- Gamers will go to great lengths to figure out ways in which they can break a game they're trying to set records for (or sometimes just to find interesting secrets).
- There are ways in which you can make educated guesses about how a game is coded and then test those hypotheses to find glitches.
- There are ways to look at the nuts and bolts of how the game actually works, and again if you have decent programming knowledge this can help you to "break the game".