Limited observability is the key challenge in post-silicon validation and can be alleviated by using an on-chip trace buffer which monitors and captures the response of certain selected signals during run-time. Use of on-chip trace buffers for debug introduces area overhead along with increased power consumption. This imposes a constraint on the number of signals selected to be traced. In this work, we review some trace signal selection algorithms proposed in the literature and propose several new heuristics. Given the constraints on the width (number of signals traced) and depth (number of cycles over which they are traced), these algorithms attempt to select the best set of signals to maximize the state restoration ratio. We evaluate the quality and performance of these heuristic signal selection algorithms while using two different techniques for state restoration: the forward propagation and backward justification (FB) method and the satisfiability (SAT) based method.