Can I use Wally or Evosoda on a Snorlax to search my deck, even though there is {currently} no evolution of Snorlax?
No, there has to at least be the possibility of a valid evolution in order to use this card. Sorry.
Source: TPCi Rules Team (2018-07-26)
If I use Evosoda to evolve my Basic Pokemon into a Stage 1, can I then use Wally to further evolve it into a Stage 2 on that same turn.
Yes, but be careful of the order in which you play the cards. Wally says you can use it on a Pokemon that was put into play this turn, but Evosoda says you cannot use it on a Pokemon that was put into play this turn. So you can play Evosoda first then Wally, but you cannot play Wally then Evosoda (on the same Pokemon, of course).
Source: TPCi Rules Team (2017-03-16)
Can I use Evosoda on a Caterpie the first turn of the game or the turn that Caterpie is played since "Adaptive Evolution" says it can evolve in those cases?
No, you can't use Evosoda to evolve in either of those conditions because the text on Evosoda specifically prevents it.
Source: TPCi Rules Team (2014-05-29)
Can I use Evosoda to search for a Mega Pokemon?
As long as it evolves from the Pokemon you choose, yes.
Source: XY FAQ (2014-02-06), TPCi Rules Team (2014-02-06)
If a Basic Pokemon was put into play last turn, can I use Evosoda on it twice to bring it all the way to a Stage 2?
No, you cannot. When you evolve a Pokemon it is a new Pokemon, and since it was put into play this turn you cannot use Evosoda on it until next turn.
Source: XY FAQ (2014-02-06), TPCi Rules Team (2014-02-06)