You do so by going to the Day Care at Route 3 and putting two compatible Pokemon together there. You can only do this once you've beaten the game, because Sky Arrow Bridge is not accessible until after you've defeated the Champion.
And no, you don't need a nursery at the Join Avenue. The nursery just helps you hatch eggs faster, but you can just do that by getting on your bike and having a Pokemon w/ Flame Body in your party (I used Volcarona) and cycling up and down the Sky Arrow Bridge.
