Declare the variable with defvar. There is no other way to remove the warning, and it is really considered good practice.
Your intention to keep the symbol table uncluttered is worthy, but you are not actually doing so. I think you have misunderstood the semantics of variable bindings in Emacs Lisp, since you seem to believe that by not declaring it foo-state will be unbound in any buffer not using foo-mode. That is not the case.
In Emacs Lisp names (aka symbols) are global. As soon as foo-state is evaluated the first time, the runtime creates a new symbol object for foo-state and puts this into the global symbol table (aka obarray). There are no local symbol tables, so it does not matter where foo-state is evaluated and how, foo-state refers to the same symbol object at any place (see Creating Symbols).
Each symbol object consists of components (aka cells), one of which is the variable cell (see Symbol components). setq modifies the current binding of the system, on top-level without lexical binding this effectively changes the variable cell of the symbol object, thus the global value of the variable. Again, it does not matter where setq is evaluated. Actually if some bar-mode evaluated (setq foo-state "bar"), foo-state would be bound to "bar" in foo-mode too, and vice versa.
Thus the only effect of (defvar) over (setq) it that documents the intention of using a symbol as global variable, so telling others to not modify this variable unless manipulation of the behavior of foo-mode is intended. You can attach documentation to the variable, and mark as being defined in your buffer (C-h v foo-state will provide a link to jump to the definition).
Since Emacs Lisp lacks namespaces and is – by default – dynamically scoped, documentation is fundamentally important to avoid conflicts between modules. If I wrote a bar-mode using your foo-mode I might accidentally bind to foo-state, call foo-change-state and then see my mode misbehaving because a variable was unintentionally overwritten. Declaring foo-state doesn't make this impossible, but it at least allows me to catch the error, because C-h v foo-state will reveal that this variable is used by another mode, so I'd better not use it unless I really intend to manipulate that mode.
As a last word: In all of the aforementioned text “mode” can be replaced with Emacs Lisp files. modes are nothing special with regards to symbols. All of the above also holds for Emacs Lisp that do not declare modes, but just contain a bunch of functions.
(elisp) Warning Tips<kbd>RET</kbd> – phils Apr 6 '14 at 21:30C-h i g (elisp) Warning Tips RETis where the documentation which answers this question lives. – phils Apr 8 '14 at 3:34define-derived-mode, as in(define-derived-mode foo-mode nil "foo" "My nice major mode." (set (make-local-variable 'foo-state) "bar")). – Stefan Apr 16 '14 at 1:03Warning Tipssection in the Emacs Manual contains a blatant lie regardingdefvar: "Such a definition has no effect except to tell the compiler not to warn about uses of the variable [...] in this file.". It most certainly can have more impact than just silencing the compiler: "[it] also declares the variable as "special", so that it is always dynamically bound even if ‘lexical-binding’ is t." (quote taken from the actual documentation fordefvar). Perhaps the advice inWarning Tipswas written before the introduction of lexical binding in Emacs Lisp... – ack Mar 1 at 13:27