A miner just needs to know an address to send the coins to as well as a source of entropy (such as intermittent network connections). The miner then generates a throw-away private key/address pair. Upon coin creation, the coins are spent in the same transaction block to the destination address. As has been noted in other threads, the destination wallet does not even have to be on an Internet-connected computer.
Edit: To avoid refunded coins (and a non-empty virtual wallet), Transaction fees should be payed out of fees paid to the miner in the transaction block; likely (approximating) a user-configurable percentage. Errata: miner processing the transaction can decide which transactions are included or not: no fees necessary.