Hmm. Seems this term has also been snagged by Microsoft... I'll put up a description of what I understand by a stateless object:

More precisely an object without mutators - a state-changeless object.

aka ImmutableObject

Compare these two date implementations:

 # stateful
 class Date:
	def __init__( self, year, month, day ):
		self.year = year
		self.month = month
		self.day = day

	def advanceday( self ):
		self.day = self.day + 1
		if self.day > daysinmonth( month, year ):
			self.day = 1
			self.month = self.month + 1
			if self.month > 12:
				self.month = 1
				self.year = self.year + 1

 # stateless
 class Date:
	def __init__( self, year, month, day ):
		self.year = year
		self.month = month
		self.day = day

	def nextday( self ):
		day = self.day + 1
		if day > daysinmonth( month, year ):
			day = 1
			month = self.month + 1
			if month > 12:
				year = self.year + 1
				month = 1
			else:
				year = self.year
		else:
			month = self.month
			year = self.year
		return Date( year, month, day )

----
In relation to MicrosoftTransactionServer a StatelessObject is an object that ''doesn't'' hold private state accumulated from the execution of one or more client calls.[1]

----
A StatelessObject is a collection of [hopefully] related subroutines.

''...which is why it's not a real object; it's just a collection of related functions.'', See UtilityClasses.

'''Not strictly true. An MTS object can hold state between client calls. See Enable/Disable Commit.'''

'''Nevertheless stateless is THE one and only way to get high performance, and is why MS hold most of the TPC-C records.'''

How does using a StatelessObject improve performance over a StatefulObject?

''It can be copied and cached without losing semantics.''
----
Stateless objects that are nothing but buckets for subroutines are one of the causes of RavioliCode.

'that are nothing but buckets for subroutines' is the key. You can get quite some useful effects from StatelessObject''''''s. Consider e.g. the object True and False deriving from boolean (as in SmallTalk).

* Constants aren't stateless objects. The objects True and False have states ''true'' and ''false'' respectively.
** But not mutable state; they're ValueObject''''''s.

----
I know at least one VB developers who thinks that because MTS demand StatelessObject''''''s, they must be a good thing in themselves. So he writes two types of classes,  Stateless objects that contain all the processing logic and classes with just get and let properties that might as well be Types. He seems to be rather proud of this.
----
Just to get away from the Microsoft bashing, please look at Java Servlets. They are more stateless than MTS objects.

''But servlets are (or should be) communication utilities that link the incoming message/request to the application. They don't exist except as intermediaries for the message.''

''In small or narrow applications they can be used to perform logic, as the SimplestThingThatCouldPossiblyWork but this restricts growth.''
----
A stateless object is a subroutine library. See Java Math for an egregious example.

Oops!  Java Math isn't so much a stateless object as an objectless object.
----
See ImmutableObject, ValueObject, ValueObjectsShouldBeImmutable, MonostatePattern
----
External Links
* http://www.boyet.com/Articles/StatelessObjects.html