Semi-molten rock appears at the bottom of the magma sea, but it also forms a (mostly) solid layer between the magma sea and the deepest parts of the map, the area colloquially known as the circus, which is extremely dangerous. Further information is a spoiler; look it up on the wiki if you don't care about that. The magma sea, and the caverns, are big open spaces, but that doesn't mean that there's no solid connection between their tops and bottoms; there are always columns and such that link above and below a layer. If you're (un)lucky, you can dig straight through the center of one of these columns without breaching and revealing the caverns or magma sea.
Finding magma should be a matter of going up somewhat from where you found semi-molten rock. If you want to find magma safely, dig outwards every 3-4 z-levels from your shaft until you encounter warm stone, then stop and dig towards the same place 1 z-level above where you found warm stone. If you find warm stone again, stop and go another z-level up. Otherwise, once you're above the last place you found warm stone, dig down staircases to reveal the magma.
Digging through semi-molten rock is one of the most dangerous undertakings available in the game. Further information is not available here (though the danger is not an unkillable magma megabeast, egglaying or otherwise, and in fact is survivable with preparation). As long as you're above the SMR, however, you're mostly safe; the critters that swim in magma aren't very dangerous.