The most obvious stringy signature would be the observation of Regge resonances at energies close to the string scale. If the extra dimensions are very large, i.e. string scale is very low (I'm extremely skeptical about this possibility), such signatures could even be observed by the LHC. See this paper for the detailed computations of the scattering amplitudes and the crossections: http://arxiv.org/abs/0807.3333. Read the summary at the end of the paper.
A more generic/less specific, prediction is the existence of superpartners at some scale below the string scale. In the phenomenologically interesting scenarios, e.g. Calabi Yau compactifications of the Heterotic string, one obtains some type of N=1 D=4 supergravity. Unfortunately, there is no unique prediction for the details of the sparticle spectrum because there exist different mechanisms of supersymmetry breaking and the spectrum depends on that. However, in such compactifications, one generically expects some type of gravity mediation possibly mixed with high scale gauge mediation. Furthermore, one also has to specify in which corner of M-theory one is working, e.g. Heterotic, Type IIB, Type IIA, M-theory on G2, F-theory etc, which results in certain restrictions on the form of the superpotential and the Kahler potential. For example, in the G2 corner without fluxes the superpotential is purely non-perturbative because all the compactification moduli enjoy the PQ symmetry inherited from the gauge symmetry of the 11D supergravity 3-form. Thus, one can make a generic statement that the Yukawa couplings will have exponential hierarchies and the scale of SUSY breaking may be exponentially suppressed relative to the Planck scale. Furthermore, in this sector SUSY breaking is naturally gravity mediated because in 7 dimensions the 3-cycles supporting visible and hidden sectors generically do not intersect, etc. Once the mechanism of SUSY breaking and the M-theory patch are specified, one may be able to compute the sparticle spectrum at the string/GUT scale and put strong constrains on it from the top down and combine those with the bottom up requirements. In this way one can get several testable scenarios parameterized by very few phenomenological dials. The whole exponentially large landscape issue may be effectively decoupled when one is interested in these types of questions (SUSY breaking and the sparticle spectrum). To be more specific about the last point, in Type IIB flux vacua, the contribution of the fluxes to the superpotential can take on an exponentially large number of values, however, the corresponding F-terms for the complex structure moduli are still zero and the only phenomenologically relevant parameter will be the value of the flux superpotential, which is just one input parameter, whose detailed microscopic dependence on the fluxes is irrelevant for the computation of the sparticle spectrum!
Another generic prediction of string compactifications comes in the imprint of the non-trivial topology on the particle spectrum in 4D. In particular, string compactifications typically imply the existence of a number of particles with similar properties. The multiplicity of SM generations is one such example and while it's still not clear why there are only three generations, it's clear that having multiple generations is generically expected. Of particular interest are so-called axions, which are ultra-light pseudoscalar particles - the partners of some (or all in the G2 case) of the geometric moduli. One of these axions can naturally provide a dynamical solution to the strong CP problem and the PQ symmetry that makes it so light can be directly traced back to the gauge symmetry of the corresponding RR-type field in 10D. Depending on the topology, there may actually be hundreds of such particles whose existence would be a complete mystery from the 4D effective field theory point of view. The experimental implications of such an "Axiverse" is described in detail here: http://arxiv.org/abs/0905.4720
On a related note, in a generic compactification one also expects a large number of moduli fields - scalars in 4D EFT. These fields gain large masses (generically at or well above the gravitino mass scale) and interact with the visible sector via Planck suppressed operators. Their presence can have a major impact on cosmology because some of the geometric moduli end up as light as the gravitino and can be quite long-lived if SUSY breaking scale is low. They may therefore come to dominate the energy density of the universe after inflation and the standard thermal cosmological history must be revised. This is a very active area of research and there are many good papers on the topic.