Opponent has {Windswept Heath} on board, and I have {Aether Vial} on board with 2 counters. At the end of my turn he activates the fetch and goes to search, I flash in {Leonin Arbiter} with {Aether Vial}. Does he still get to search or is it null and void?
Your opponent gets priority back after your Leonin Arbiter enters the battlefield at which point your opponent has the opportunity to pay the 2. If the opponent can't or chooses not to, then the fetch ability will resolve and your opponent will be unable to search, but will still shuffle their library.
So the fetch ability uses the stack then?
Yes. All activated abilities use the stack.