If you really wanted to make your players mad, you could put some sort of message that appeared to be really important but in the end turned out to really be some angst filled NPCs bad poetry or something...
heheh. No. That would be wrong.
I'd say: maps, warnings, secret messages, symbols that mean something but need to be decoded, or have been smudged , leaving your PCs with a puzzle to figure out. That can be great for expanding plot.
But also mix in non important stuff too, like initials of past folks who've been there, symbols that mean nothing, Mean WereRats Suck!, so and so the bard and his band ROCK! etc...
OK, silly there at the end...but you don't want to make everything on the walls of the dungeon mean something because that would be way too easy, and where's the fun in that?
~Sheri