Yes, the Trace can detect Apparition. According to Mad-Eye in DH Chapter 3:
"He's made it an imprisonable offense to connect this house to the Floo Network, place a Portkey here, or Apparate in or out. ...
"The Trace, the Trace!" said Mad-Eye impatiently. "The charm that detects magical activity around under-seventeens, the way the Ministry finds out about underage magic! If you, or anyone around you, casts a spell to get you out of here, Thicknesse is going to know about it ...
"We're going to use the only means of transport left to us, the only ones the Trace can't detect, because we don't need to cast spells to use them ..."
So according to the first paragraph I quoted above, Mad-Eye has already considered, and rejected, both Portkeys and Apparition; according to the second and third paragraphs, the Trace is the means by which Thicknesse would find out whether a spell had been cast to get Harry away from the Dursleys' (and therefore the reason Mad-Eye rejected those means of transport).
So that seems pretty clear: the Trace can detect Apparition. But can it detect where you're Apparating to?
I knew there was a quote about not being able to track where someone is Apparating to, and tracked it down in DH chapter 11, where Lupin says, "It's impossible to track anyone who Apparates, unless you grab hold of them as they disappear!" However, that may not be relevant here, because Lupin said that after Harry turned seventeen; he was assuming that the Trace was not in play.
We do know, from Mafalda Hopkirk's letters to Harry in CoS and OotP, that the Trace does indicate the location where a spell is cast. (In CoS chapter 2, the letter says "... a Hover Charm was used at your place of residence this evening ..."; in OotP chapter 2, the letter says "... you performed the Patronus Charm at twenty-three minutes past nine this evening in a Muggle-inhabited area and in the presence of a Muggle.")
In the case of Apparition, the Trace would certainly indicate the place you were leaving (since that's where you were when you cast the spell), and might or might not show the place you were going. So when Harry and Dumbledore headed to the cave, the Trace might have just shown them leaving Hogsmeade. But on the way back, it would certainly have shown them leaving the sea by the cave.
But that's assuming the Ministry was monitoring Harry's Trace at the time. Since he was (supposed to be) at school, it's very possible that they weren't -- there would be too many false positives from all the magic going on around Hogwarts all the time. Even though the Trace could show his location, and therefore give away the fact that he was away from school while using magic, the Ministry clearly doesn't watch that too closely -- if they did, Harry would have gotten a letter for using magic in the Shrieking Shack back in PoA. So while the Ministry could have used the Trace to tell where Harry and Dumbledore went, it's not likely that they did so.
As for your question about why they didn't walk a block and then Apparate... I've wondered that too! But in fact, that's effectively what they did: they flew a ways, and then used a Portkey. Since the prohibition (weasel-worded so as to appear legitimate) was only on magical transport to and from the Dursleys', this was fine, apart from the unauthorized Portkeys. Perhaps the idea was just to get to someplace well-warded for a quick rest before using a Portkey to get the rest of the way (which turned out to be a good idea!) Imagine if they'd walked instead, and been on the ground while the Death Eaters mounted an aerial assault.