※個人的な体感だけで書きます。

「サイト内のファイルに対して変更を施した場合」の順位に影響するまで

おそらく2週間～1ヶ月前後。
まず検索エンジンがファイルの更新に気が付くまで1日～3日。
トップページ以外の全てのファイルのキャッシュが更新されるまではそれぐらいかかる印象。

「サイト外から有効なリンクを貼った場合」の順位に影響するまで

1ヶ月～2ヶ月。
リンクを貼ったサイトが、検索エンジンにクロールされないといけない。
ただクロールされただけでは反映されていない様子。
Googleの場合、バックリンクの更新が行われれば完全に反映されたと考えていい？

サイトのPV数や訪問者数の変化

上記のように、SEOの作業はなにかと反映されるのに時間がかかるため、長い目で見ないと効果が見えない場合がある。
具体的には6ヶ月間SEO対策を行い、手ごたえを感じたとしても訪問者数に繋がらないこともある。
これはあらかじめ対策を行う前の、1ヶ月～2ヶ月でアクセスログを取っておくと改善される事が多い。
特にGoogleは時間の概念が強くなってきたので、今まで以上に時間をかけていく必要があるかもしれない。

下の図はあるサイトの1ヶ月ごとのPV数の推移。6ヶ月だけで見るとあまり変化が見えないが全体を通して見ると効果は出ていると言ってよいと思う。

あとは、季節や時代によるニーズの変化がPV・訪問者には現れます。
「5月に"ランドセル"で検索する人が減ってしまった。」
「夏に"鰤（ブリ）"で検索する人が減ってしまった。」
「2006年に"若手お笑い"で検索する人が減ってしまった。」
これは根本的にはどうにもならないことです。