I went to the cinnabar islands but he isn't there. Where'd he go?
It's on Seafoam Island (or in it, since it's a cave). Surf right from Cinnabar to get to it.
Fondant is right. If you go up the ladder you enter Blaine' s gym and if you go down you (post story) find Articunio.