The CMS Experiment at the CERN LHC is getting ready for its initial search for physics beyond the Standard Model (SM). Among the many possibilities, the search for supersymmetric particles is the most promising. The associated production of s-quarks and gluinos is predicted to have a large cross section. One of the experimental signals of this process would include missing transverse energy, jets, and a Z reconstructed by two opposite-sign muons. This signal would have a small SM background, making it one of the CMS reference analyses during the first run of the accelerator. Another possibility is the direct observation of heavy stable charged particles (HSCP), predicted by some SUSY models and also by extra-dimension models. These particles being very massive, long-lived and electrically charged should leave tracks in the muon detectors with a reconstructed velocity significantly smaller than c. If HSCPs exist, they could be observed directly, which makes their search very exciting. In this talk, phenomenological and experimental aspects of the CMS search for s-quarks, gluinos and HSCPs will be presented.