Calcium is a key signaling agent in animals and plants. Its involvement in the regulation of a wide range of processes has led to the question of how calcium signals can activate stimulus-specific responses. We introduce a computational framework for studying intracellular calcium signaling using elements of information theory. We use mutual information to quantify the differential activation of proteins in response to different calcium signals to provide an operational definition of specificity. Using optimization procedures this framework allows us to explore the biochemical determinants of calcium decoding. We explore simple toy models and general binding kinetics approaches to demonstrate the utility and limitations of the proposed framework. Unravelling signaling specificity is key for understanding information processing within cells and for the future design of synthetic nanodevices for molecular communications.