For anyone who is trying to do it without modifying your ViewModels AND not loading all your records from the database.

Repository

    public List<Order> GetOrderPage(int page, int itemsPerPage, out int totalCount)
    {
        List<Order> orders = new List<Order>();
        using (DatabaseContext db = new DatabaseContext())
        {
            orders = (from o in db.Orders
                      orderby o.Date descending //use orderby, otherwise Skip will throw an error
                      select o)
                      .Skip(itemsPerPage * page).Take(itemsPerPage)
                      .ToList();
            totalCount = db.Orders.Count();//return the number of pages
        }
        return orders;//the query is now already executed, it is a subset of all the orders.
    }

Controller

    public ActionResult Index(int? page)
    {
        int pagenumber = (page ?? 1) -1; //I know what you're thinking, don't put it on 0 :)
        OrderManagement orderMan = new OrderManagement(HttpContext.ApplicationInstance.Context);
        int totalCount = 0;
        List<Order> orders = orderMan.GetOrderPage(pagenumber, 5, out totalCount);
        List<OrderViewModel> orderViews = new List<OrderViewModel>();
        foreach(Order order in orders)//convert your models to some view models.
        {
            orderViews.Add(orderMan.GenerateOrderViewModel(order));
        }
        //create staticPageList, defining your viewModel, current page, page size and total number of pages.
        IPagedList<OrderViewModel> pageOrders = new StaticPagedList<OrderViewModel>(orderViews, pagenumber + 1, 5, totalCount);
        return View(pageOrders);
    }

View

@using PagedList.Mvc;
@using PagedList; 

@model IPagedList<Babywatcher.Core.Models.OrderViewModel>

@{
    ViewBag.Title = "Index";
}

<h2>Index</h2>
<div class="container-fluid">
    <p>
        @Html.ActionLink("Create New", "Create")
    </p>
    @if (Model.Count > 0)
    {


        <table class="table">
          <tr>
            <th>
                @Html.DisplayNameFor(model => model.First().orderId)
            </th>
            <!--rest of your stuff-->
        </table>

    }
    else
    {
        <p>No Orders yet.</p>
    }
    @Html.PagedListPager(Model, page => Url.Action("Index", new { page }))
</div>

Bonus

Do above first, then perhaps use this!

Since this question is about (view) models, I’m going to give away a little solution for you that will not only be useful for paging, but for the rest of your application if you want to keep your entities separate, only used in the repository, and have the rest of the application deal with models (which can be used as view models).

Repository

In your order repository (in my case), add a static method to convert a model:

public static OrderModel ConvertToModel(Order entity)
{
    if (entity == null) return null;
    OrderModel model = new OrderModel
    {
        ContactId = entity.contactId,
        OrderId = entity.orderId,
    }
    return model;
}

Below your repository class, add this:

public static partial class Ex
{
    public static IEnumerable<OrderModel> SelectOrderModel(this IEnumerable<Order> source)
    {
        bool includeRelations = source.GetType() != typeof(DbQuery<Order>);
        return source.Select(x => new OrderModel
        {
            OrderId = x.orderId,
            //example use ConvertToModel of some other repository
            BillingAddress = includeRelations ? AddressRepository.ConvertToModel(x.BillingAddress) : null,
            //example use another extension of some other repository
            Shipments = includeRelations && x.Shipments != null ? x.Shipments.SelectShipmentModel() : null
        });
    }
}

And then in your GetOrderPage method:

    public IEnumerable<OrderModel> GetOrderPage(int page, int itemsPerPage, string searchString, string sortOrder, int? partnerId,
        out int totalCount)
    {
        IQueryable<Order> query = DbContext.Orders; //get queryable from db
        .....//do your filtering, sorting, paging (do not use .ToList() yet)

        return queryOrders.SelectOrderModel().AsEnumerable();
        //or, if you want to include relations
        return queryOrders.Include(x => x.BillingAddress).ToList().SelectOrderModel();
        //notice difference, first ToList(), then SelectOrderModel().
    }

Let me explain:

The static ConvertToModel method can be accessed by any other repository, as used above, I use ConvertToModel from some AddressRepository.

The extension class/method lets you convert an entity to a model. This can be IQueryable or any other list, collection.

Now here comes the magic: If you have executed the query BEFORE calling SelectOrderModel() extension, includeRelations inside the extension will be true because the source is NOT a database query type (not an linq-to-sql IQueryable). When this is true, the extension can call other methods/extensions throughout your application for converting models.

Now on the other side: You can first execute the extension and then continue doing LINQ filtering. The filtering will happen in the database eventually, because you did not do a .ToList() yet, the extension is just an layer of dealing with your queries. Linq-to-sql will eventually know what filtering to apply in the Database. The inlcudeRelations will be false so that it doesn’t call other c# methods that SQL doesn’t understand.

It looks complicated at first, extensions might be something new, but it’s really useful. Eventually when you have set this up for all repositories, simply an .Include() extra will load the relations.