Febreeze usually works to get rid of most weird smells (cigarette smells included) on pillows and stuffed toys, but you may find that it'll make the toy or pillow a bit 'sticky.' I've done this before, and what worked was Febreeze and then a long drying period.
Once it's dry, I soaked the pillow/toys in baking soda, water and added a cup of white vinegar for half an hour. Then I washed it as normal (detergent) and let it to dry. That eliminated the smokey smell for me completely.
Hope that helps!