This will depend on how often your device contacts the IceTV server to update its remote scheduling information. For most devices the time between updates is set by the IceTV server and is about 15 minutes (unless the IceTV server is under heavy load). So if you schedule something to record it'll normally happen within the next 15 minutes, maybe sooner.
This also assumes that your recorder is on (and not asleep or in standby mode) and for Media Centers that the IceTV Interactive application is running in the background (this can be checked by looking in the System Tray (down the bottom near the time) and seeing if the IceTV Interactive icon is listed, its a blue circle with a white star in it).
There are some devices that don't use the IceTV servers default settings, one example is the Elgato EyeTV software, the quickest EyeTV will update is once every hour (this is an option with the preferences of EyeTV).
Another thing worth noting is that if you schedule something that's over 5 days away, it won't be sent to your device straight away... it'll be sent when it's start time falls within the next 5 days. This is done intentionally as some of the software we work with doesn't like scheduling programs if there's no EPG data downloaded for that program yet (ie. the remote record request arrives before the EPG data does).