They come back at the rate of one a day, they'll pop up randomly around your island.
Yes, if you eat fruit you destroy rocks instead of spanging them for goodies. Fruit count at the top left. If you find a toilet you can crap out the fruit! You can also spade up entire trees and pop them in your pocket when you're hopped up on fruit - each tree will use up one fruit. You can plant them again immediately if you like. That'll come in useful later :)
"Local islands" actually means "Other people with Switches playing AC right now, in your wifi range". "Remote islands" means other people's islands but over the Internet, and you'll need Nintendo Online (£19/year) to do that, and friends who have their islands open, or people who have shared their Dodo Code.
What you need is a random island trip to hit rocks and pick up resources! You need to go to residential services, go to the Nook Stop machine, redeem 2000 Nook Miles on a Nook Miles ticket, and take that back to the airport and Orville will point out that you have it on you - there's a new chat menu entry to use it.
Have fun! You can get as many of those Nook Miles Tickets as you like, as long as you have miles.