Simon's answer got the basic idea right and got my vote, but I think his answer left many problems intact, and may not have given enough details to actually do the method extraction.

Note the following:

• In the retrieveHistory method jedis was not being used, which became obvious after refactoring.

• By getJedisObjectFromPool and returnJedisObjectToPool is called through a new method doWithRedis so that you need not remember to add the finally block each time. (This method can be moved to JedisHelper class, which seems to be its natural home.)

• Single return statements, declaring variable at the top of the method, and Yoda conditionals are C archaisms. The do not do you any good in Java. And just make your code much harder to read.

I could go over anything you might want elaborated, until then here is the code:

public String retrieveHistory(final JSONObject data) {

    final ServletContext context = ContextManager.getContext();

    final String defaultResult = new JSONObject().toString();

    try {
        String key1 = data.getString("key1");
        String key2 = data.getString("key2");
        String channel = key2 + "_" + data.getString("channel-id");

        LOGGER.info("History requested for " + channel
                + " belonging to subkey: " + key2);

        if (!jedisHelper.checkValidity(key1, key2)) {
            LOGGER.info("Invalid Keys or keys deactivated");
            return defaultResult;
        }

        if (data.has("timestamp")) {
            String timestamp = data.getString("timestamp");
            return retrieveHistoryByTimestamp(context, channel, timestamp).toString();
        }

        if (data.has("count")) {
            String count = data.getString("count");
            return retrieveHistoryByCount(context, channel, count).toString();
        }

        return defaultResult;

    } catch (JSONException ex) {
        LOGGER.error("JSON Exception: " + ex);
        return defaultResult;
    } catch (NumberFormatException ex) {
        LOGGER.error("NumberFormatException: " + ex);
        return defaultResult;
    }
}

private JSONObject retrieveHistoryByTimestamp(final ServletContext context,
        String channel, String timestamp) {

    NavigableMap<Long, String> myHistory = getHistory(context, channel);

    if (myHistory != null) {
        return getHistoryFromContextByTimestamp(timestamp, myHistory);
    }

    return getHistoryFromRedisByTimestamp(timestamp, channel);
}

private JSONObject retrieveHistoryByCount(final ServletContext context,
        String channel, String count) {
    NavigableMap<Long, String> myHistory = getHistory(context, channel);

    if (myHistory != null) {
        return getHistoryFromContextByCount(count, myHistory);
    }

    return getHistoryFromRedisByCount(count, channel);

}

private JSONObject getHistoryFromContextByTimestamp(String timestamp,
        NavigableMap<Long, String> myHistory) {
    JSONObject object = new JSONObject();

    final Map<Long, String> channelHistory = myHistory
            .tailMap(Long.parseLong(timestamp));
    if (!channelHistory.isEmpty()) {
        for (Map.Entry<Long, String> entry : channelHistory
                .entrySet()) {
            object.put(String.valueOf(entry.getKey()),
                    entry.getValue());
        }
    }

    return object;
}

private JSONObject getHistoryFromContextByCount(String count,
        NavigableMap<Long, String> myHistory) {
    JSONObject object = new JSONObject();
    final Map<Long, String> channelHistory = myHistory
            .descendingMap();

    if (!channelHistory.isEmpty()) {
        int counter = 0;
        final int i = Integer.parseInt(count);

        for (Map.Entry<Long, String> entry : channelHistory
                .entrySet()) {
            if (counter >= i) {
                break;
            }
            object.put(String.valueOf(entry.getKey()),
                    entry.getValue());
            counter++;
        }
    }

    return object;
}

private JSONObject getHistoryFromRedisByTimestamp(final String timestamp, final String channelId) {

    return doWithRedis(jedisHelper, new JedisCallback<JSONObject>() {
        @Override
        public JSONObject call(Jedis jedis) {
            LOGGER.info("get history from redis");

            if (timestamp != null && !timestamp.isEmpty()
                    && !"0".equals(timestamp)) {
                Set<Tuple> set = jedis.zrangeByScoreWithScores(channelId, timestamp,
                        String.valueOf(System.currentTimeMillis()));
                if (set != null) {
                    return new JSONObject(set);
                }
            }
            return new JSONObject();
        }
    });

}

private JSONObject getHistoryFromRedisByCount(final String count, final String channelId) {

    return doWithRedis(jedisHelper, new JedisCallback<JSONObject>() {
        @Override
        public JSONObject call(Jedis jedis) {
            LOGGER.info("get history from redis");

            if (!"0".equals(count)) {
                try {
                    final int limit = Integer.parseInt(count);
                    Set<Tuple> set = jedis.zrevrangeByScoreWithScores(channelId, "+inf",
                            "-inf", 0, limit);
                    if (set != null) {
                        return new JSONObject(set);
                    }
                } catch (NumberFormatException ex) {
                    LOGGER.error("Exception in returning history from Redis: " + ex);
                }
            }

            return new JSONObject();
        }
    });

}

private NavigableMap<Long, String> getHistory(
        final ServletContext context, String channel) {
    @SuppressWarnings("unchecked")
    ConcurrentHashMap<Object, Object> history = (ConcurrentHashMap<Object, Object>) context
            .getAttribute("history");
    if (null == history) {
        history = new ConcurrentHashMap<Object, Object>();
        context.setAttribute("history", history);
    } 

    @SuppressWarnings("unchecked")
    NavigableMap<Long, String> myHistory = (NavigableMap<Long, String>) history
            .get(channel);

    if (myHistory == null) {
        LOGGER.info("History for this channel not found in Context");
        history.put(channel, new ConcurrentSkipListMap<Long, String>());
    }

    return myHistory;
}


interface JedisCallback<T> {
    T call(Jedis jedis);
}

private static <T> T doWithRedis(JedisHelper jedisHelper, JedisCallback<T> callback) {
    Jedis jedis = null;
    try {
        jedis = jedisHelper.getJedisObjectFromPool();
        return callback.call(jedis );
    } finally {
        if (jedis != null) {
            jedisHelper.returnJedisObjectToPool(jedis);
        }

}
}

EDIT

Note that after the refactoring only multiple returns you have that is not either - when validating parameters - when checking if a method returned null and we cannot continue

is in the outermost method. Which we cannot eliminate as I did eliminating historyType dispatch parameter. Maybe you can if you know at the calling site whether you want to call with count or timestamp.