I'm not sure it's made explicit in canon, but we can probably make a decent guess.
Both Hogwarts correspondence and individual mail seems to be capable of being addressed in minute detail.
He crossed to the window and opened it; Hermes flew inside, landed on
Ron's essay and held out a leg to which a letter was attached. Ron
took the letter off it and the owl departed at once, leaving inky
footprints across Ron's drawing of the moon Io.
'That's definitely
Percy's handwriting,' said Ron, sinking back into his chair and
staring at the words on the outside of the scroll: Ronald Weasley,
Gryffindor House, Hogwarts. He looked up at the other two. 'What d'you reckon?
'Open it!' said Hermione eagerly, and Harry nodded.
—Harry Potter and the Order of the Phoenix
Petunia Dursley receives a similar letter when the Dursleys are about to throw Harry out:
'Let go of it, Petunia!' roared Uncle Vernon. 'Don't touch it, it
could be dangerous!'
'It's addressed to me,' said Aunt Petunia in a shaking voice. 'It's
addressed to me, Vernon, look! Mrs Petunia Dursley, The Kitchen,
Number Four, Privet Drive -
She caught her breath, horrified. The red envelope had begun to smoke.
—Harry Potter and the Order of the Phoenix
However, the three instances that we know of in which a letter was minutely addressed were both official correspondence of a sort: letters from Hogwarts to Harry, and a letter from Percy (at the time a high-up Ministry employee) to Ron, and a letter from Dumbledore (headmaster of Hogwarts) to Petunia Dursley.
I think it likely that this is reserved for official correspondence. That's not to say that a private individual couldn't do things this way, of course, but Harry and others always seem to address their letters by hand.
It is also true that many magical missives seem to be able to find their targets without the sender knowing the recipient's location. For example, Harry is able to send letters to Sirius via Hedwig in Goblet of Fire, even though he does not know Sirius's location.
I suspect that the address must be automagically generated when the letter nears its recipient. After all, if Percy were able to know the location of anyone in Hogwarts from hundreds of miles away, that would seem like a pretty big security loophole in the protective spells surrounding the castle. If the Ministry could simply generate a letter with Sirius's precise location on it, catching him would certainly be a lot easier.
I think it more likely that the address is simply generated upon arrival, or something along those lines.
Owls, of course, are very good at getting letters to people, even when the sender knows nothing about the recipient's address (as in Harry's case). Sirius must have had some additional security, obviously, to prevent just any owl from tracking him down, but it is not difficult to conceive what this might be (something like the spells Hermione used to hide the Trios's exact location in Deathly Hallows).
The key thing is that letters can have magically detailed addresses without allowing the sender to know anyone's location; in fact, this seems most consistent with the way such mail works in the books.
In the case of Harry's letter to Sirius, first, we don't know that Harry hasn't placed a spell on the envelope to render it nicely addressed when it arrives, and second, doing so would not necessarily give him Sirius's location.