I asked this question and the answer was "in the Battle Mansion", I click on the link, then the link to the Battle Mansion, but it doesn't say how, so how?
Currently, it's not really that proven (because it's a new game and all), but the known requirement is that you need to win 200 battles straight for a Starf Berry. 100 battles straight will win you a Lansat berry.
Source: Game FAQ
