In this paper, we address the problem of deploying sensors to estimate the state of a plant described by discrete-time fractional-order system. More specifically, we assume that these systems' parameters and disturbance/measurement noise characteristics describe possible scenarios. Therefore, the goal of this paper is that of selecting a subset of sensors that will optimally perform (in a minimum squared error sense) among multiple (finite) scenarios. In particular, we show this problem to be NP-hard, and we provide a bisection-type algorithm with suboptimality guarantees. Furthermore, we show that no other algorithm ensures better optimality bound for this problem unless P=NP. Finally, we present some simulations that illustrate the applicability of the main results in an electroencephalogram data associated with different tasks.