Note The accepted is perfectly fine - but wanted to add a version4 example because they are different enough. 
Nav.js
  import React from 'react';
  import { Link } from 'react-router';
  export default class Nav extends React.Component {
    render() {    
      return (
        <nav className="Nav">
          <div className="Nav__container">
            <Link to="/" className="Nav__brand">
              <img src="logo.svg" className="Nav__logo" />
            </Link>
            <div className="Nav__right">
              <ul className="Nav__item-wrapper">
                <li className="Nav__item">
                  <Link className="Nav__link" to="/path1">Link 1</Link>
                </li>
                <li className="Nav__item">
                  <Link className="Nav__link" to="/path2">Link 2</Link>
                </li>
                <li className="Nav__item">
                  <Link className="Nav__link" to="/path3">Link 3</Link>
                </li>
              </ul>
            </div>
          </div>
        </nav>
      );
    }
  }
App.js
  import React from 'react';
  import { Link, Switch, Route } from 'react-router';
  import Nav from './nav';
  import Page1 from './page1';
  import Page2 from './page2';
  import Page3 from './page3';
  export default class App extends React.Component {
    render() {    
      return (
        <div className="App">
          <Router>
            <div>
              <Nav />
              <Switch>
                <Route exactly component={Landing} pattern="/" />
                <Route exactly component={Page1} pattern="/path1" />
                <Route exactly component={Page2} pattern="/path2" />
                <Route exactly component={Page3} pattern="/path3" />
                <Route component={Page404} />
              </Switch>
            </div>
          </Router>
        </div>
      );
    }
  }
Alternatively, if you want a more dynamic nav, you can look at the excellent v4 docs: https://reacttraining.com/react-router/web/example/sidebar
Edit
A few people have asked about a page without the Nav, such as a login page. I typically approach it with a wrapper Route component
  import React from 'react';
  import { Link, Switch, Route } from 'react-router';
  import Nav from './nav';
  import Page1 from './page1';
  import Page2 from './page2';
  import Page3 from './page3';
  const NavRoute = ({exact, path, component: Component}) => (
    <Route exact={exact} path={path} render={(props) => (
      <div>
        <Header/>
        <Component {...props}/>
      </div>
    )}/>
  )
  export default class App extends React.Component {
    render() {    
      return (
        <div className="App">
          <Router>
              <Switch>
                <NavRoute exactly component={Landing} pattern="/" />
                <Route exactly component={Login} pattern="/login" />
                <NavRoute exactly component={Page1} pattern="/path1" />
                <NavRoute exactly component={Page2} pattern="/path2" />
                <NavRoute component={Page404} />
              </Switch>
          </Router>
        </div>
      );
    }
  }