On your ViewModel you want to have a property:
private object content;
public object Content
{
get { return content; }
set
{
this.content = value;
OnPropertyChanged("Content");
}
}
Then in your main window (or where your content is to be hosted) add a ContentControl:
<ContentControl Content="{Binding Path=Content}"
HorizontalContentAlignment="Left"
VerticalContentAlignment="Center"
Focusable="False"/>
The main ViewModel would maintain a list of known ViewModels (View All, Search) and set the Content property to one of these ViewModels in the appropriate command execution, the Add New command would probably create a new instance of the AddNewViewModel and set the Content property.
In the View where the ContentControl is located put some data templates in the Resources mapping the ViewModels to the appropriate views:
<DataTemplate DataType="{x:Type vm:AddNewViewModel}">
<AdornerDecorator>
<views:AddNewView DataContext="{Binding}"/>
</AdornerDecorator>
</DataTemplate>
This is the basic pattern I am using in a Wizard that I am working on at the moment.