How expensive is it to change the OpenGL state by calls to glTexParameter, glEnable, glTexEnv and so forth. Are they just logical states which doesn't change any internal structure until rendering starts (and change is needed) or can some of these functions be time-consuming at the moment you call them?

In general, yes it is expensive, and you should avoid unnecessary state changes as much as possible. A good way to do this is to sort batches by state and render them in that order.

In practice different state changes will take different amounts of time, and this will vary depending on drivers and hardware. Do some profiling and you should be able to find out which changes are most expensive on your hardware at least.

There is a cost in some cases, but I've found that it's actually usually an extremely slight cost. As long as you do what benjamin_bunny suggested, and even if you don't, you should be fine. Don't sacrifice visual quality in order to reduce the number of state changes.

From my practical experience with the Nvidia drivers, changing soem states, such as enabling/disabling textures have no noticeable penalty.

I have a rendering system that uses q3-style shaders which means lots of shader stages with different states. 10k triangles with 5-10 stages without any state management, just plain trianglepushing, wasn't very efficient. Sorting by shader and drawing all triangles for a stage at a time improved the speed about 100%.

This was perhaps a slightly extreme situation, but state changes should be considered very expensive. Especially calls to glBindTexture(), if you would consider that a state change.

But as has already been mentioned the best way to find out is to run a profiler and see for yourself.