@bubu,
I would also like to know what part of speech 'all over' functions as in all the sentences above.
First things first, Bubu. It's an adverb phrase. It describes 'where'.
There is mud all over the floor.
This one means that there is mud in many places on the floor. It doesn't have to mean 100% covered. In fact people often use this phrase in an exaggerated fashion simply for emphasis
The floor is mud all over [is this one correct?]
It's a possibility though I'd say that the word order isn't as common as the first one, above. Imagine after a hurricane or a flood and the floor is completely c0vered with a layer of mud. It could be used in that case.
My shirt is all over mud.
This is not a common word order and as such it sounds "foreign". With the addition of a comma, a pause in speech, you could have,
My shirt is, all over, MUD!
and it could be used in an emphatic fashion.