Hi,
Yes, the details on the encoder will be important. If it has a fine encoder disc then it might be too fast for the PICaxe, but at least you shouldn't have any problems with contact bounce. Also the AB sequence might be: 00 , 01, 11 , 10 .... or 00 , 01 , 10 , 11 .. or perhaps something else. But the important thing to realise is that you are looking for changes in the signal(s), so you need code which stores a "last value" (position) to compare with the "present value".
I'm afraid I may have over-simplified the stepper motor. Firstly there are two types (unipolar and bipolar). The unipolar usually have 4 coils (5 wires), but are "easier" to drive; the bipolar only have 4 wires but it is necessary to reverse the direction of current flow in the (two) coils. Also, it is usual to drive two coils at a time, e.g. A+B then B+C then C+D then D+A , etc., or sometimes with more complex patterns.
Do you actually need to sense and drive the motor in both directions? Does the motor need to exactly replicate the steps from the encoder? It might be easier to start by driving the motor in only one direction, and perhaps using just one of the encoder outputs (A or B). There have been a few threads concerning code for encoders, but often the main issue has been overcoming "contact bounce". Code to drive the stepper may be easier, when the type of motor has been identified.
Cheers, Alan.