Apparently, under some configurations (I think they are compile settings dealing with the locale), PostgreSQL will not, by default, use an index for LIKE queries. First of all, note that PostgreSQL will NEVER use an index for an ILIKE query (case-insensitive like). For that, you should use a functional index using the LOWER function. It will also not use an index if the LIKE starts with a wildcard. But, for queries that *end* in a wildcard, if you set it up right, you can get PostgreSQL to use an index.
Anyway, apparently the problem is that PostgreSQL doesn't know what locale it is in, and therefore doesn't know how to order the characters. Therefore, you have to give it some help. After your index column, you need to add text_pattern_ops. So, for my own table, I did the following:
create index entity_lower_name_idx on entities(lower(name) text_pattern_ops)
And viola! Postgres is now using the index. Since this is a functional index, it indexes queries like
select * from entities where lower(name) like 'hello%'
Hope that helps someone! I received the information here and here.