You need to set up an index using sets or sorted sets that you write to when you save anything.
There’s a good writeup at http://web.archive.org/web/20121013063245/http://playnice.ly/blog/2010/05/05/a-fast-fuzzy-full-text-index-using-redis that is pretty close to what I use myself.