Here is a circuit that might do the trick for you. I'm not overly enthused by it, but it doesn't use a lot more than you originally required.
D1 is a zener diode, perhaps a 4V device? Q1 is a BC547 or similar (depending on the relay) The diode shown across the relay is required. It would be a 1N4001. Diode D2 is a 1A schottky diode. The value of R1 is probably around 100 ohms
Q1 starts to switch on switch on when the solar panel produces around 4.6V. When it turns on hard enough (probably around 5V), it will pull in the relay, powering the circuit from the solar panel.
When the voltage from the solar panel falls, the relay will drop out, powering the device from the battery.
Diode D2 prevents a loss of power from the device during switching. During this time, the device is powered from the solar panel.
There are some serious drawbacks. Firstly, the load from the device is likely to cause the voltage from the solar panel to fall dramatically. This will cause the relay to drop out. Then the voltage will rise and the relay will pull in, this will repeat until the solar panel can provide enough power to drive the load. It may cause the device some headaches, and may even remove power from the device for long enough to cause it to reset.
On the basis of the above, I don't think this is practical.
There are better solutions, but they're more complex.
Perhaps someone can come up with something that is both simple and reliable...