Как определить наличие закодированной информации методом стеганографии в файле bmp, выбранным на угад?

никак :) В этом и суть (правда не уверен, что стеганографию можно называть методом, это скорее название самого явления, когда передаётся скрытое сообщение).

Информация может быть закодирована где угодно: в отдельных пикселях, в каких-то заранее оговоренных последовательностях пикселей, в заголовках файла, в метаданных файла и т. д. Так, как стеганография обычно используется в паре с криптографией, бессмысленно даже пытаться какие-то шаблоны искать, которые могут соответствовать какому-то адекватному сообщению, ведь оно может быть закодировано так, что будет представлять из себя в чистом виде набор непонятных кракозябр. А ещё, если Вы не знаете посредством чего сообщение интерпретируется, то Вы и не будете знать что вообще там можно искать, ведь там может быть скрыта картинка, может быть текст, а может быть какой-то набор звуков (типа голосового сообщения).

Единственное, что Вы можете попытаться сделать - поискать на изображении артефакты, которых там быть не должно и которые обычно воспринимаются как помехи и банальная порча картинки. Однако и тут не факт, что Вы их найдёте, ведь изображение может рисоваться специально под сообщение, фотографии итак содержат множество артефактов (особенно сделанные на дешёвые фотики), а огромный выбор картинок в интернете позволит подобрать такую, на которую скрытое сообщение почти никак не повлияет :)

Короче гарантированно никак. Только если сам шифратор допустит ошибку, которую можно обнаружить.

в стеганографии по методу LSB распределение младших значащих бит пикселов отличается от гауссового. Или как-то так. Это конечно не гарантия что она там есть, но повод заподозрить.
На практике - в картинках в которых точно есть стеганография, удалось проявлять всякие квадратно-гнездовые структуры с помощью регулировки яркости/насыщенности/оттенка в графическом редакторе.