It's never explained in detail (at least, not that I recall), but the Worms are segmented, just like the ones you may have encountered in the real world. They move by contracting and expanding their segments, with small spikes (yes, worms really have them) assisting the process. They don't (so far as I recall, although some later books seem to contradict this, and the early books DO mention them eating Sand Plankton) open their mouths and process sand all of the time, the way a worm will tend to do with Dirt, however, they have the advantage of moving thru sand, which is considerably easier to 'push aside', given their size and weight. (The Square-Cube law may make this impossible in RL, for something that size, but given that Frank Herbert never goes into detail, there may be more there than we know of.)
Regardless; they are SciFi Monsters -- some suspension of Disbelief is needed :)
Some worms do stay close to the surface, but some go very deep; there are references in the third book (if I'm remembering correctly) to a worm going deep and sulking after being ridden hard.
Edit - From 'Children of Dune' -
"The worm tired before dawn. Leto slid off its side and watched it dig itself into the dunes, moving slowly in the familiar pattern of the creatures. It would go deep and sulk."
That being said, there is an implied limit to how deep they go; from later in 'Children of Dune',
"It sensed only the sandtrout and would not attack the deep-sand vector of its own kind."
That implies that Sandtrout go deeper than full-blown worms.