Since Skyla says "Search your deck for a Trainer card", does this allow me to search for any kind of Trainer including Supporters, and Stadiums?
Yes, it does. The current definition of "Trainers" includes Items, Supporters, and Staduims.
Source: Boundaries Crossed FAQ (2012-11-08), TPCi Rules Team (2012-11-08)

Relevant cards

Note: All applicable cards may not be listed below.
BW7_134
BW7_149
SWSH2_166
SWSH2_166
XY8_148
XY9_122