These are both fine:
1. They started their show immediately.
2. They immediately started their show.
This one has a different meaning:
3. They immediately started to their show.
In older English, it would have meant "They immediately set off for their show". However, that meaning of "start to" is no longer current; and it wouldn't make much sense, in this context!