He is found in the basement of Wayward Cave. To get to the basement, get TM70 Flash as well has HM Strength. There is a hidden entrance under Cycling Road. Enter it, and use Strength. Proceed down the stairs. Then, you can find Gible.
