Constance gives you her quests after a certain number of chats with her, and each "-chat-" topic takes a bit of time with her in the party for it to appear. I often find that if I go out and get into a bunch of combats with her in the party, a new -chat- topic will appear. You will know when it does because Constance's greeting will say something like "I'm bored %PCName, how about having a little chat?" and the topic will appear. After each chat, the topic disappears again and you have to wait a certain amount of time before the next -chat-.
I believe Constances gives you her quests after roughly 8-10 chats. She definitely earns several more abilities (i.e. creating lockpicks, scrolls, paralyze spell, etc.) before the chat giving you her quests appears.
Once she gives you her quests, it's fairly straightforward to complete it.