This is a capacitive-type sensor. Its capacitance (and thus, its impedance) changes with humidity, and somewhat also with temperature.
Therefore, frequency accuracy is another factor you should consider. I believe the Picaxe's internal clock is far more accurate than any external RC based oscillator.
That is what I would do:
1) Use the Picaxe's PWM output. Also use 1 Khz, since the device is characterized at that frequency.
2) The PWM wizard indicates that these values are outside range. What you could do is use a CD4013 as a divide by 4, which will also provide a perfectly symetrical square wave. The PWM frequency would be now 4 Khz. From the wizard, this equals to pwmout 2 , 249, 500
3) Filter it with a 2 pole RC filter. Buffer the signal with an opamp before feeding it to the sensor.
4) The sensor will form the upper leg of a voltage divider, the bottom leg being a resistor whose value is halfway between the sensor's upper and lower resistance range.
5) Rectifiy the signal with a precision rectifier, and feed it to the PICAXE's ADC.
That is the hardware part, the software follows.
6) Since the device has a lot of temperature dependency, it would be worthwhile to include a temperature sensor and perform some temperature correction.
7) Also the device is highly non-linear. Some sort of curve fitting correction would be nnecessary. I don't know how to do this with the integer math. Maybe other gurus know.
All in all, this is a handful, and looks like a very challenging (read: fun) project. If you need help with the analog portion of the circuits, feel free to ask.