Question

Where do I find a Lucky Egg in HeartGold/SoulSilver?

Answer 1

Wild Chansey have a 5% chance of holding Lucky Egg. You can find Chansey on Route 13, 14, and 15, plus the Safari Zone with objects. Normally, Chansey has a 1% chance of appearing, but this increases to 40% during swarms. Swarms are chosen at random each day, so you can use the DS clock to cycle the swarm until you get Chansey.

Also, a Pokemon with the Pickup ability from level 41-60 has a 1% chance of picking up a Lucky Egg.

Comments

Plus with that Pickup thing, which is better I say as you have a 1% chance of finding Chansey and then only a 5% chance of it holding a Lucky Egg.

---

So Basically go level up your pokemons and don't bother trying to get one, Right!?

---

You will probably find one within a couple of hours if you cycle the swarm onto Chansey. If you're actually going to sit down and level grind, then that time should not be daunting at all.
You can also use RNG manipulation to get one, which is less difficult than it sounds and gives you a very good skill if you want to do teambuilding in this game. Look it up on YouTube.

Answer 2

In Pokemon Heartgold you have to find a Chansey or a Blissey that is holding it. There is a 5% chance chansey or blissey will be holding one.