Does every Symbol in Mathematica induce a monad?

Mathematica provides a perfect way to define monad by setting UpValues and DownValues of some symbol. Please, find specifications for monads Maybe and State below.

1. Monad Maybe:

   DownValues[Just] = {Just[(a: Just[x_])] :> Just[x]};
   UpValues[Just] = 
       {(expr: (op: Except[Just | List | Trace | UpValues | DownValues])[
          a___, Just[b_], c___]) /;  
          !MatchQ[
              Unevaluated[expr],
              HoldPattern[If[__, __, Just[x_]] | If[__, Just[x_], __]]
          ] :> Just[op[a, b, c]]};
   

   Rule from DownValues[Just] stands for monad Maybe multiplication law. That is removing of head duplicates. Rule from UpValues[Just] stands for bind operation of monad Maybe. One need to use special pre-condition for this pattern because Mathematica uses some wrapping code to convert evaluating/reducing expression in standard form by low-level call MakeBoxes. For example, let's see this wrapping code:

   Hold[
    If[False, 3,
     With[{OutputSizeLimit`Dump`boxes$ =
        Block[{$RecursionLimit = Typeset`$RecursionLimit},
         MakeBoxes[Just[3], StandardForm]
         ]
       },
      OutputSizeLimit`Dump`loadSizeCountRules[]; 
      If[TrueQ[BoxForm`SizeCount[OutputSizeLimit`Dump`boxes$, 1048576]], 
       OutputSizeLimit`Dump`boxes$,
       OutputSizeLimit`Dump`encapsulateOutput[
        Just[3],
        $Line,
        $SessionID,
        5
        ]
       ]
      ],
     Just[3]
     ]
    ]
   

   That's why rule from UpValues[Just] has special pre-condition for being inside of condition expression. Now one can use symbol Just as a head for computations with exceptions:

   UpValues[Nothing] = {_[___, Nothing, ___] :> Nothing};
   Just[Just[123]]
   (*
    ==> Just[123]
   *)
   
   Just[123] + Just[34] - (Just[1223]/Just[12321])*Just[N[Sqrt[123]]]
   (*
    ==> Just[155.899]
   *)
   

   Thanks to @celtschk for great comments of this point.

2. Monad State:

   return[x_] := State[s \[Function] {x, s}];
   bind[m_State, f_] := State[r \[Function] (f[#[[1]]][#[[2]]] & @ Part[m, 1][r])];
   runState[s_, State[f_]] := f[s];
   

   For monad State I didn't use UpValues and DownValues just for similarity with Haskell notation. Now, one can define some sequential computation as State value with complex state logics as a monadic computation by using return and bind operations. Please, see an example:

   computation =
     Fold[bind, return[1], 
      Join[{a \[Function] s \[Function] {a, a + s}, 
        b \[Function] s \[Function] {b, s + b/(3 s)}, 
        c \[Function] s \[Function] {c, s + (s^2 + c)}},
       Array[x \[Function] a \[Function] s \[Function] {a, s}, 300]
       ]
      ];  
   

   To get more effective computation one can use runState operation:

   Fold[#2[#1[[1]]][#1[[2]]] &, runState[23, return[1]], 
       Join[{a \[Function] s \[Function] {a, a + s}, 
             b \[Function] s \[Function] {b, s + b/(3 s)}, 
             c \[Function] s \[Function] {c, s + (s^2 + c)}},
            Array[x \[Function] a \[Function] s \[Function] {a, s}, 3000]
     ]
    ]
    (*
     ==> {1, 3119113/5184}
    *)
   

Conclusion:

1. Ideas of rule-based programming and using Head as type identifier allow user to express any(?) programming concept in Mathematica. For example, as it has just been shown, monads State and Maybe from Haskell;
2. Using of UpValues and DownValues for assigning rules to symbols and using of generalized operations (such as bind is) allow user to put expressions in different monadic environments.

Perhaps this alternative approach is useful? Many years ago, before I stumbled on this site, I wrote a package for monad comprehensions with parallel generators (think Thread), which I found a very useful feature of early Haskell compilers and missed in MMA. I simply implemented the formal semantics given in a paper I found on the topic. I added some syntax with the Notation package which allows me to write things such as:

SetAttributes[comprehend,HoldRest]

comprehend[m_, e_, True]:= unit[m][e]
comprehend[m_, e_, q_]  := comprehend[m,e,q,True]

comprehend[m_,e_,generator[p_,l_],q__]:=
  Module[{ok}, ok[_]:=zero[m]; ok[p]:=comprehend[m, e, q]; bind[m][ok,l]]

comprehend[m_,e_,zipgen[gens__],q__]:=
  Block[{x},
    comprehend[m, e, 
      generator[comprehend[m,x,generator[generator[x_,_],    
        {gens}]], 
           zipping[m][comprehend[m,l, generator[generator[_,l_],{gens}]]]],q]]

(*  assume everything not a generator or a parallel generator is a test *)
comprehend[m_,e_,b_,q__]:=If[b,comprehend[m,e,q],zero[m]]

zero[Maybe] := None
unit[Maybe] := Some
bindMaybe[_,None] := None
bindMaybe[f_,Some[x_]] := f[x]
bind[Maybe] := bindMaybe
zipping[Maybe] := (Message[comprehend::nozip,Maybe];zipping[])

zero[List]:={}
unit[List]:={#}&
bind[List]:=Flatten[#1 /@ #2,1]&
zipping[List]:=Thread

pluck[e_,l_] := Block[{x},comprehend[List,x,generator[x_,l],x=!=e]]

removeDups[{}] := {}
removeDups[{h_,l___}] := Prepend[pluck[h,removeDups[{l}]],h]

zero[Sets] := {}
unit[Sets] := {#}&
bind[Sets] := removeDups[Flatten[#1 /@ #2,1]]&
zipping[Sets] := (Message[comprehend::nozip,Sets];zipping[])

zero::usage="The zero of a monad (if any)";
unit::usage="The unit of a monad";
bind::usage="The bind function of a monad";
zipping::usage="The zipper for a monad (if any)";
comprehend::usage="A monad comprehension (requires a zero)";
zipgen::usage="The constructor for parallel generation";
generator::usage="The constructor for generation";
comprehend::nozip="Zipping not implemented for `1`";
removeDups::usage="Remove duplicates from a list";
Maybe::usage="The (name of the) Maybe monad";
Sets::usage="The (name of the) Set monad";

I'd be interested if anyone finds this adds something useful.

Does every Symbol in Mathematica induce a monad?

Yes, the monad laws are satisfied for every symbol in Mathematica with List being the unit operation and Apply being the binding operation.

So, does Mathematica provide a natural maybe-like monad for every symbol [...]

In view of the monad laws satisfaction table above the answer is "yes, kind of."

[...] and does it provide a natural framework for any explicit monadic computations?

I would say the answer is "yes" to this question. I think this way of programming of the Maybe monad is fairly straightforward.

A general approach for working with monads is described in the blog post "Monad code generation and extension" (or see Markdown version at GitHub.) That approach does not take the "algebraic type" perspective on monad programming, it uses code generation instead.