Occasionally, I turn my ignition key and the starter does not kick in (no solenoid sound either). At the same time I find the gear change lever is locked. If I release the emergency brake and rock the truck, the gear change lever frees up and the ignition switch activates the starter.

Where do I start?

 

Google: ford ranger loose column shifter

See if that seems like the problem, usually an easy fix just tightening some screws, this is a very common issue on all Ford trucks with column shifters

The transmission must be in Park or Neutral for the starter motor to work, the switch for this is on the drivers side of transmission, its call the DTR(digital transmission range) sensor
Black plasic box on the shift rod
If the shift cable is loose in the cab then DTR doesn't show Park so no starter motor

Can't shift out of Park is different
On the shifter rod in the cab is the interlock solenoid, it is power on by the brake pedal switch, its part of brake light switch but a different section of the switch
When in Park key off a pin is inserted into shift rod so it can't move out of Park
With key on the brake pedal switch is powered on, when you press down on the brake pedal this switch powers up the solenoid which pulls the pin out and allows you to shift out of Park

Google: 1997 ford ranger interlock solenoid

These things could be related IF(big if) the shift rod in the column is your problem, these can get loose or break, loads of labor to repair or replace