I read that a few people were having a problem with this so I wanted to post a (somewhat) elegant solution I came up with while trying to deal with this. The problem is when you create templated pages in Silverlight and the ContentControls do not have the parent Frame's NavigationService (it's always null when you try and use it). There are similar scenarios where a NavigationService is present in intellisence but is always null. To enable site-wide Navigation:
Create a new UserControl (I called mine 'NavFrame') that has a Navigation Frame in it (I called mine 'RootFrame').
Inside this Frame you can set whatever content you like.
Set this UserControl as your RootVisual in App.xaml.cs (i.e. this.RootVisual = new NavFrame();).
To use the NavigationService in any of your pages you can type something like:
((NavFrame)App.Current.RootVisual).RootFrame.NavigationService.Navigate(new Uri("Your Uri", UriKind.RelativeOrAbsolute));