GolfScript, 83 chars

n%{' '%{1\{'A#BC D EF G'?+}/.}%$(+2/{~- 12%}%.(+.(+]$0=.$]10,7>?'MMaijnoorr

'>2%}%

This is a quick first solution; I'm sure this can be golfed further. Passes the bash test suite, after fixing the bug pointed out by flodel in the comments.

Edit 1: Saved 5 chars with a shorter way to recognize the canonicalized major and minor chord patterns.

Edit 2: Saved 2 more chars with more compact output encoding inspired by grc's solution. (Thanks!) As a side effect, the code now prints an extra blank line after the output, but the test harness seems to accept that, so I guess it's OK. :)

Here's how it works:

• The outer loop n%{ }%n* just splits the input into lines, runs the code inside the braces for each line and joins the results with newlines.

• ' '% splits each line into an array of notes. For each of those notes, 1\{'A#BC D EF G'?+}/ then converts that note into a semitone number by searching for each of its characters in the string 'A#BC D EF G' and adding up the positions (which will be -1 for any character not found in the string, notably including b). (I'm sure I've seen this trick used before.) Finally, the . duplicates each number, so that, at the end of the loop, e.g. the input F Ab C has been turned into [9 9 0 0 4 4].

• We then sort the notes with $, move the first note to the end with (+, and split the array into pairs with 2/, so that it now looks e.g. like [[9 0] [0 4] [4 9]]. Then {~- 12%}% maps each pair of notes into its difference modulo 12, turning our example array into [9 8 7].

• Next, .(+ makes a copy of the array and rotates its elements left by one position. We do this twice and collect the copies into an array with ], so that our example now looks like [[9 8 7] [8 7 9] [7 9 8]].

• We then sort this array of arrays with $ and take the first element — in this case [7 9 8] — with 0=. We then make a copy of this array (.), sort it ($), collect both the unsorted and the unsorted array into another array of arrays (]), and search for the first occurrence of the array [7 8 9] (which is written as 10,7> to save two chars) in it.

• This gives us either 0 (if the unsorted array was [7 8 9], and thus the chord is major), 1 (if the unsorted array was a permutation of [7 8 9], which, given that its first element must be smallest, can only be [7 9 8], making the chord minor) or -1 (if even the sorted array does not equal [7 8 9]).

• This number is then used as a starting index into the string "MMaijnoorr\n\n" (where the \ns are given as actual linefeeds in the code), from which we take that character and every second subsequent one as the output. If the index is -1, we start from the last character of the string, which is just a line feed.

Python, 160

f='A#BC D EF G3453543'.find
try:
 while 1:x,y,z=sorted(map(lambda x:f(x[0])+f(x[1:])+1,raw_input().split()));print'MMianjoorrr'[f(`y-x`+`z-y`)/14:-1:2]
except:0