Gollum probably met her (sorry, Her) when he was first allowed to escape from Mordor. He promised her to bring her more food probably at that time. Maybe he did bring her food from then on, as he was witnessed entering Cirith Ungol some times (re: Shagrat & Gorbag's talk), and grew more and more accustomed to her. Until he brought her Frodo & Sam.
|