Regularly, when I roll for random encounters underground or outdoors in a game, I allow for the possibility that some kind of clue to an encounter happens instead. For example, if rolling a d6 for an encounter, a real encounter happens on a 1 and a clue happens on a 2. In my hex-stocking wilderness system, there's also provision for clues, though on a less frequent basis than real encounters.
I usually make the clues up on the spot. They fall into two kinds: sights and sounds, which can occur even when the party is stationary; and leavings, which the party has to be moving to find. Here are some examples.
Sights: A pair of griffins flying across the sunset, many miles away.
In the night, a brief red glow, sighted across a far-away ridge line (red dragon).
Sounds: Snatches of shouting and song down in the valley (bandits).
A full-throated roar echoing across the plains (lion).
Far away, echoing through many passages, a door slams (dungeon monster - ogre, perhaps?)
Leavings can be...
Body parts: The cast-off skin of a giant snake.
Manticore spikes, embedded in a tree.
Victims: A dead squirrel, withered and drained of all blood (stirges).
The bones and equipment of a former adventurer, scattered all through a long corridor (gelatinous cube).
Tracks: A long wide trail of half-dried slime, bending around a corner (giant slug).
Large hoofprints, going across the road (gorgon).
Smells and vapors: The slight stench of rotting flesh in the air (zombies).
A smoky haze hanging in the air (hell hounds).
Environment damage: A scorched spot on the dungeon wall (hell hounds).
The tracks lead into a trodden and torn clump of thorn bushes (gorgon).
Intentional markings: Obscene graffiti on the wall, written in Dark Rune pictograms (humanoids).
A strong musky scent around the base of a tree (giant wolverine).
I find that using clues this way adds suspense to adventures, gives players options (do we investigate this, or run like hell?), and makes for more meaningful information than most random "dungeon dressing" out there.