My standard way of doing this is to expose a "ViewState" property from the view model (normally an enum). The view then binds to the property and uses the visualstatemanager to switch to appropriate visual states depending on the enum.
The DataStateSwitchBehavior from the Expression Samples is a good example on how to do the switching to visual states.
EDIT In response to comment
First off, when dealing with VisualStates use Blend (no one should be forced to write that much XAML by hand). I believe it's even on all(most?) of the MSDN subscriptions.
Using Visual States starts with Visual State Manager
<VisualStateManager.VisualStateGroups>
<VisualStateGroup x:Name="GroupOne">
<VisualState x:Name="Normal"/>
<VisualState x:Name="Searching"/>
</VisualStateGroup>
</VisualStateManager.VisualStateGroups>
You'd typically add this to the layoutroot.
The visual state manager consists of a collection of StateGroups which in turn consists of a collection of VisualStates.
The groups keep mutually exclusive states organised, since you can have multiple visual states active at any one time but only one state from each group. The standard pattern is to have a empty state called something like "Normal" or "Default" to be used turn off the other states. A Base state basically.
In your case you would then have a "Searching" visual state which would contain a storyboard which would disable various buttons, activate busy animations etc.