Problema com java.lang.OutOfMemoryError:

Não, um singleton não é necessariamente uma solução.
Na verdade evite-os ao máximo possível.

Você provavelmente tem um memory leak em mãos, rode um profiler na sua aplicação para detectar o ponto do problema, provavelmente essa sua consulta está instanciando objetos demasiadamente e não os desaloca quando se deve.
Enfim, reveja o que está sendo feito, COMO está sendo feito e considere o uso de um profiler para encontrar esse gargalo.

Considere isso como um exercício de uma situação “real life”

Blz, vou fazer isso. (Sem singleton)
Mas só uma coisa. Eu realmente vacilei aqui (não estou desalocando nada nessa página)
No caso, um simples ListaDeColunistas = null; desalocaria esse objeto sem problemas?

Se a lista ficar fora do escopo, ela é desalocada.

Tente rodar o profiler como o colega indicou. Outra coisa, verifique se você está fechando corretamente os statements e conexões.

Exatamente.
Outra coisa a se questionar é: preciso mesmo disso tudo de objetos? O usuário quer mesmo visualizar 500 quinquilhões de registros?
Preste muita atenção se está liberando esses recursos, seja em conexões, statements, etc a objetos inutilizados.

Ok, farei isso.
Obrigado aos dois!!

E quanto aos 500 quinquilhões
Essas duas listas são sempre pequenas, uma com no máximo 30 itens e a outra com uns 8 no máximo.

E reparei aqui. As listas estavam no escopo global.

Cuidado que coisas static são as grandes vilãs em termos de leak. Variáveis static nunca saem de escopo, então devem ser setadas para null explicitamente em algum momento. Na verdade, elas geram tanto problema que devem ser evitadas na medida do possível.

Pô, disso eu não sabia. Valeu pela dica.
Não me lembro de usar isso, mas vou até dar uma repassada no código procurando.

Como é uma aplicação web verifique se há coisas desnecessariamente em escopo de sessão.
Como dizemos acima, mas vale reforçar: evite variáveis estáticas, singletons e escopo de sessão.
Esses são recursos que devem ser usados apenas na presença de adultos hehe, ou seja, quando se souber exatamente qual o seu funcionamento, as conseqüências que isso trará ao sistema e ter analisado várias alternativas que se mostraram inviáveis.

Ok.

Bom, de escopo de sessão eu estou usando apenas um Bean Gerenciado pra verificar se o usuário está logado ou não.
Mas o melhor jeito de fazer isso é assim mesmo certo?

Bom, existem frameworks que fazem isso sem que você tenha que gerenciar “na mão” quem tá logado e quem não está.
MAAS se for fazer isso manualmente acredito que isso justifique um ManagedBean em escopo de sessão.
Mas lembre-se de mantê-lo ao mínimo e somente ao que lhe interessa, ou seja, se ele serve pra controlar usuário ele conterá dados referentes apenas a usuários e comportamento apenas referente ao usuário, nada além!

Bom, nesse Bean eu tenho os dados do usuário e alguns métodos que utilizo para deixa-lo editar seu perfil e coisas do tipo.

Lembrei que estou criando outro Bean de sessão pra fazer a administração do site. No caso tenho que verificar se o administrador está logado. Mas também tenho alguns objetos que são usados nessa administração.

Mas tudo que está em um bean de sessão é alocado uma única vez certo?
No caso do login de usuário (uma vez para cada usuário, mas esse bean é bem pequeno)