Спасибо большое за помощь!
Мне удалось сформировать подпись текстового сообщения, использовав нужный ключевой контейнер.
На стороне сервера подписывается xml-файл с помощью следующего кода 
 public static bool SignXmlDocument(string document)
        {
          X509Store store = null;
          try
          {
            // Находим секретный ключ по сертификату в хранилище MY
            store = new X509Store("My", StoreLocation.CurrentUser);
            store.Open(OpenFlags.OpenExistingOnly | OpenFlags.ReadOnly);
            SignSettings ss = new SignSettings();
            ss.GetSignSettings();
            X509Certificate2Collection fcollection = (X509Certificate2Collection)store.Certificates;
            X509Certificate2Collection collection;
            collection = X509Certificate2UI.SelectFromCollection(fcollection,
                                                                   "Выберите сертификат",
                                                                   "Выберите сертификат для подписания документа.", X509SelectionFlag.SingleSelection);
              
            if (collection.Count == 0)
              return false;
            X509Certificate2 Certificate = collection[0];
            Gost3410CryptoServiceProvider cert_key = Certificate.PrivateKey as Gost3410CryptoServiceProvider;
            if (cert_key != null)
            {
                byte[] dummyHash = new byte[32];
                cert_key.SignHash(dummyHash);
            }
            //CreateSomeXml("doc_to_sign.xml");
            // Открываем ключ подписи.
            AsymmetricAlgorithm Key = Certificate.PrivateKey;
            // Создаем новый XML документ.
            XmlDocument doc = new XmlDocument();
            // Форматируем документ с игнорированием пробельных символов.
            doc.PreserveWhitespace = false;
            // Читаем документ из файла.          
            string xEl = System.IO.File.ReadAllText(document);
            XElement xel = XElement.Load(new System.IO.StringReader(xEl));
            xel.Element("Signer").Add(new XElement("CertificateNumber", Certificate.GetSerialNumberString()));
            xel.Element("Signer").Add(new XElement("CertificateExpirationDate", Convert.ToDateTime(Certificate.GetExpirationDateString()).ToString("dd.MM.yyyy")));
            string post = String.Empty;
            string FIO = String.Empty;
            GetFIOAndPostFromSert(Certificate, ref post, ref FIO);
            xel.Element("Signer").Element("SignerName").SetValue(FIO);
            xel.Element("Signer").Element("SigningDate").SetValue(DateTime.Now.ToString("dd.MM.yyyy HH:mm"));
            xel.Element("Signer").Element("SignerPosition").SetValue(post);
            //doc.Load(new XmlTextReader(document));
            //doc.Load(new XmlTextReader("doc_to_sign.xml"));
            doc.LoadXml(xel.ToString());
           
            // Создаем объект SignedXml по XML документу.
            SignedXml signedXml = new SignedXml(doc);
            // Добавляем ключ в SignedXml документ. 
            signedXml.SigningKey = Key;
            // Создаем ссылку на node для подписи.
            // При подписи всего документа проставляем "".
            Reference reference = new Reference();
            reference.Uri = "";
            // Явно проставляем алгоритм хеширования,
            // по умолчанию SHA1.
            reference.DigestMethod =
                CPSignedXml.XmlDsigGost3411Url;
            // Добавляем transform на подписываемые данные
            // для удаления вложенной подписи.
            XmlDsigEnvelopedSignatureTransform env =
                new XmlDsigEnvelopedSignatureTransform();
            reference.AddTransform(env);
            // Добавляем transform для канонизации.
            XmlDsigC14NTransform c14 = new XmlDsigC14NTransform();
            reference.AddTransform(c14);
            // Добавляем ссылку на подписываемые данные
            signedXml.AddReference(reference);
            // Создаем объект KeyInfo.
            KeyInfo keyInfo = new KeyInfo();
            // Добавляем сертификат в KeyInfo
            keyInfo.AddClause(new KeyInfoX509Data(Certificate));
            // Добавляем KeyInfo в SignedXml.
            signedXml.KeyInfo = keyInfo;
            // Можно явно проставить алгоритм подписи: ГОСТ Р 34.10.
            // Если сертификат ключа подписи ГОСТ Р 34.10
            // и алгоритм ключа подписи не задан, то будет использован
            // XmlDsigGost3410Url
            //if (signedXml.SignedInfo.SignatureMethod == null)
            //  signedXml.SignedInfo.SignatureMethod =
            //      CPSignedXml.XmlDsigGost3410Url;
            // Вычисляем подпись.
            signedXml.ComputeSignature();
            // Получаем XML представление подписи и сохраняем его 
            // в отдельном node.
            XmlElement xmlDigitalSignature = signedXml.GetXml();
            // Добавляем node подписи в XML документ.
            doc.DocumentElement.AppendChild(doc.ImportNode(
                xmlDigitalSignature, true));
            // При наличии стартовой XML декларации ее удаляем
            // (во избежание повторного сохранения)
            if (doc.FirstChild is XmlDeclaration)
            {
              doc.RemoveChild(doc.FirstChild);
            }
            // Сохраняем подписанный документ в файле.
            using (XmlTextWriter xmltw = new XmlTextWriter(document.Replace(".forsign_xml", ".xml"),
                new UTF8Encoding(false)))
            {
              xmltw.WriteStartDocument();
              doc.WriteTo(xmltw);
            }
            if (SendSignPdfToStore(document.Replace(".forsign_xml", ".xml"), DateTime.Now, "", "", ""))
              return true;
            else
              return false;
           // bool r = VerifyXmlFile(document.Replace(".forsign_xml", ".xml"));
           // return r;
          }
          catch (Exception ex)
          {
            LogWriter.Write(String.Format("SignXmlDocument({0}) {1}", document, ex.Message));
            MessageBox.Show("Ошибка при создании подписи.", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);
            return false;
          }
          finally
          {            
            if (store != null)
              store.Close();
          }
        }
        
        
        Весь код просматривать необязательно, главное, что подпись xml тут производится не просто как подипсь текствоого сообщения. Если я подписываю тот же xml файл как строку со стороны клиента, то подпись не верифицируется со стороны сервера и наоборот, видимо разные алгоритмы. То есть подпись xml имеет свои особенности и это не просто подпись строки (хеш подписываемых данных у нас совпадает, подписываем мы точно одно и то же). Не совсем понимаю, как мне следует подписать xml, чтобы он верифицировался на сервере (на клиенте моя подпись верифицируется) В примерах нет подобной объектной обработки и подписи xml (из этого я ошибочно заключила, что подписав xml как строку, получу тот же валидируемый на сервере результат). Подскажите, пожалуйста, как быть и есть ли способ описать процесс подписи на андроид-девайсе чтобы он был аналогичен коду, представленному выше и все верифицировалось.