HeartGold and SoulSilver will be released in Japan this fall, possibly on or near Nov. 21, the 10th anniversary of the original release of their namesakes. International releases will likely come in mid-2010.
Update: Pokémon Sunday has aired, revealing multiple aspects. First, there are new Sugimori artwork for the startersChikorita, Cyndaquil and Totodile. In addition, a short video of "gameplay" was shown (screenshot on the left) with overworld sprites of Gold and Silver, with the selected starter, Chikorita, walking behind Gold. There appear to be wind currents as well.