There are two different approaches, and not one "right way".
The approach that a ViewModelLocator
or similar helps with is a "View-First" approach to developing MVVM. By this, it means you start with your View in the designer, and then build the ViewModel to match. Logically, Views often create other Views, and the ViewModel is typically loaded via some form of locator and populated for a given View. Messaging or services are used to hook appropriate models into the newly generated ViewModels.
This has the advantage of being a bit easier to design visually, especially when working with Blend.
The other approach is to work "ViewModel-First". By this, you generate your ViewModels, and then use DataTemplates to have the View populate. ViewModels will compose/create other VMs, directly setting the appropriate Model. This is typically (IMO) much, much cleaner from a programmer's perspective, as things just work directly. However, it's typically more difficult to design and work with from a designer's point of view, as design-time data is more difficult to generate, etc.
Both approaches are perfectly valid, and have strong advantages and disadvantages. Different MVVM purists tend to prefer one approach over the other for various reasons - typically whether they're approaching this from a code cleanliness point of view or a designer point of view.