Where does the navigation logic belong, View, ViewModel, or elsewhere?

I a button in a view, bound to an ICommand property of the ViewModel (actually it's RelayCommand from mvvv-light)

If the user clicks on the button I want to navigate to a new view. Of course the NavigationService is part of the View not the ViewModel. That implies that the navigation is the responsibility of the View? But in my case, the view I will be going when the button is clicked depends on a great many factors, including who the logged in user is, the state the database is in, etc... Surely the View shouldn't need all that information.

What is the preferred option for executing a NavigationService.Navigate call?

If you're already using MVVM Light, one option is to make use of the message bus that it includes. So you bind your button to a RelayCommand on the view model, as you've said you're already doing. In the handler for your RelayCommand you can make the decision on which view to navigate to. This keeps all that logic in the view model.

Once your command handler has decided which view to navigate to, it can publish a message on the message bus. Your view will be listening for that message and then use the NavigationService to actually perform the navigation. So it's not doing anything other than waiting to be told to navigate somewhere and then navigating where it's told.

I've been doing this by defining a NavigationMessage class that my view models can publish, and a view base class that my views inherit from which contains the listener. The NavigationMessage looks like this:

public class NavigationMessage : NotificationMessage
{
    public string PageName
    {
        get { return base.Notification; }
    }

    public Dictionary<string, string> QueryStringParams { get; private set; }

    public NavigationMessage(string pageName) : base(pageName) { }

    public NavigationMessage(string pageName, Dictionary<string, string> queryStringParams) : this(pageName)
    {
        QueryStringParams = queryStringParams;
    }
}

This allows for simply passing the page name, or optionally also including any necessary query string parameters. A RelayCommand handler would publish this message like this:

private void RelayCommandHandler()
{
    //Logic for determining next view, then ...
    Messenger.Default.Send(new NavigationMessage("ViewToNavigate"));
}

Finally, the view base class looks like this:

public class BasePage : PhoneApplicationPage
{
    public BasePage()
    {
        Messenger.Default.Register<NavigationMessage>(this, NavigateToPage);
    }

    protected void NavigateToPage(NavigationMessage message)
    {
        //GetQueryString isn't shown, but is simply a helper method for formatting the query string from the dictionary
        string queryStringParams = message.QueryStringParams == null ? "" : GetQueryString(message);

        string uri = string.Format("/Views/{0}.xaml{1}", message.PageName, queryStringParams);
        NavigationService.Navigate(new Uri(uri, UriKind.Relative));
    }
}

This is assuming a convention where all the views are in a "Views" folder in the root of the app. This works fine for our app but of course this could be extended to support different scenarios for how you organize your views.