You need to have all 8 badges and possibly the Master Ball. Surf east from New Bark Town and you should have no problems. EDIT: Go to Ecruteak City and beat the kimono girls, then catch Ho-oh.