In this paper, we study joint queue-aware and channel-aware scheduling of arbitrarily bursty traffic over multi-state time-varying channels, where the bursty packet arrival in the network layer, the backlogged queue in the data link layer, and the power adaptive transmission with fixed modulation in the physical layer are jointly considered from a cross-layer perspective. To achieve minimum queueing delay given a power constraint, a probabilistic cross-layer scheduling policy is proposed, and characterized by a Markov chain model. To describe the delay-power tradeoff, we formulate a non-linear optimization problem, which however is very challenging to solve. To handle with this issue, we convert the optimization problem into an equivalent Linear Programming (LP) problem, which allows us to obtain the optimal threshold-based scheduling policy with an optimal threshold imposed on the queue length in accordance with each channel state.