Check out http://gamedev.stackexchange.com!
Typically, platformers use "tiles", small images that are placed in a grid, so that
- The entire background doesn't need to be stored in memory, and
- so that duplicated pieces of the background don't need to be duplicated in memory, and
- so that drawing individual pieces can be done more locally (for cache efficiency).
For example, in something like Super Mario Brothers, a huge amount of screen real estate is covered by "sky". They just have one sky tile, maybe 16x16, maybe 128x128, maybe something else entirely (but usually powers of two so the math is easy, and all tiles are the same size) that is all blue. It seems likely (to me) that their tile size is the size of one of the "blocks" that you can hit and destroy.
Anyway- so the "level data" would be an array of what tile goes in one space in the grid, probably oriented in memory as columns for locality of access too. Then when it's time to draw, you start at (for instance) the top left, then go down, then over one column and down again...
As for the "on the fly loading," that can be done but you've got to make sure that you do that loading asynchronously (so that the game doesn't pause) and that you make sure that the data that you need is available long before you actually need it.