How can I refactor this method so I don't use it in multiple places?
For this, I'll be addressing the second code snippet you've given, as it seems to be heading in the right track.

I'm assuming QueryContext is custom code, because I couldn't find any reference to it in the MSDN and you haven't provided any other tags. In a case like this it would probably be useful to see the code for this class to better optimize your usage, however I do still have a few points. The same goes with what the dataAccess variable is.

Naming

I don't like the name you've given to your second foreach loop's variable. 'p' is confusing and will be even more so if you ever expand the body of your loop. I recommend something like queryParameter.

Implicit Typing

This tends to be a personal thing, but I strongly prefer the use of 'var' when the RHS of the variable declaration makes it obvious what the type is. It saves you having to change the type in two places when refactoring. However you use it half of the time, go all in or not at all.

Out parameters

Always a sign that you should probably make a class and return it.

If you still want an explicit number of results and you don't fancy going to that effort of making a custom class, then you could always use Tuple but a custom class is preferable.

Separation of Concerns

Seems this one function is doing 2 things: building a query, and executing a query. This would be better if they were separate, which allows you more flexibility.

Results

With all this on board, your code becomes:

public class QueryResult
{
    public DataTable Data {get; set;}

    public int RecordCount {get; set;}

    public QueryResult(DataTable data, int recordCount)
    {
        this.Data = data;
        this.RecordCount = recordCount;
    }
}

public QueryResult GetRecords(Query query)
{
    DataSet results = dataAccess.ExecuteQuery(query.statement, query.parameters);
    return new QueryResult(results.Tables[0], results.Tables[1].Rows[0][0]);
}

public class Query
{
    public string Statement {get; set;}
    public Dictionary&lt;string,string&gt; Parameters {get; set;}

    public Query(string statement, Dictionary&lt;string,string&gt; parameters)
    {
        this.Statement = statement;
        this.Parameters = parameters;
    }
}

public Query BuildQuery(StringBuilder statement, string[] orderByParams, QueryContext queryContext)
{
    var parameters = new Dictionary&lt;string, string&gt;();

    if (queryContext.OrderByColumns.Count == 0)
    {
        foreach(var orderbyParameter in orderByParams)
        {
            queryContext.OrderByColumns.Add(param);
        }
    }

    if (queryContext.Parameters.Count &gt; 0)
    {
        foreach (var queryParameter in queryContext.Parameters)
        {
            dataAccess.paramAdd(parameters, statement, queryParameter.ColumnName, queryParameter.Value.ToString());
        }
    }

    // Order By Clause
    statement.Append(queryContext.OrderByColumns.GetSqlClause());

    // Apply Limit
    if (queryContext.ApplyLimit)
    {
        query.AppendFormat(" LIMIT {0},{1}", queryContext.Offset, queryContext.Limit);
    }

    return new Query(statement.ToString(), parameters);
}


You may also want to make the properties in QueryResult readonly depending on what you're hoping to do with them later.