You need to dig stairs to be able to go up and down levels. You need to dig an "up stair", and then a "down stair" below it. Or you can dig "up/down stairs" which combine both functions into the same square.
The lack of stone is probably due to embarking in an area that has clay, soil, or sand layers on top. If you tunnel down a few levels, you should find stone.
If you have an axe (which is one of the default starting items if you didn't customize them), you can (D)esignate (T)reecutting areas to chop down trees and build things out of wood (assuming you're in an area that features trees).