Discussed at

http://www.wordwizard.com/ch_forum/topic.asp?TOPIC_ID=18898

First time I had heard the expression, esp in meaning strain at the throne. As I get only 214 hits on this usage (~, toilet)I'm wondering how long the term has been used this way

That is an old word, isn't it? According to the online OED the verb form was first used in 888. The OED didn't have a reference to toileting, but the definition of "to push" or "to squeeze" would make sense.