We visited Sarawak for five nights before returning to the peninsula. We split our stay between Kubah NP (3 nights) and Permai Beach Resort (2 nights). Both were lovely but Kubah was my favourite due to its tall forest and diverse animal life.
Here are a few shots of the park from the road to Kuching:
The park has both hostels as well as nice chalets. The chalets were good value when the costs were split among the four of us.
There were several trails in the park but the best was a fairly short walk to a waterfall. The trail descended through forest with lots of big trees with buttressed roots.