how multiple threads invoke singleton object's method and work on them?

I think you have to distinguish between what you've already stored in memory and code execution.

In a Singleton Object you have:

• Fields: They are stored in memory. They can be shared amongst multiple threads and you have no guarantee they will keep consistent (unless you make them synchronized).
• Methods to be called: They can be called from more than one thread. Each execution is independent and thread safe, unless they access some shared field improperly.

Now coming to your question: if you share your singleton object among multiple threads and access it concurrently, every single thread will execute Singleton object's portion of code, wrapped in its own execution.

Also if you write a Thread.currentThread().getId(); which basically returns the thread ID you're executing into singleton's methods, you will obtain different ids, because different threads are executing their own method stack. Being stateless means you've no fields into the singleton to be shared amongst them!

A word on Stateless and Stateful

Stateless means that the bean hasn't got any modifiable field to share. That means you have only methods or/and static stuff in your object, so you can use them anywhere and will always return you same result. You don't have to worry about synchronizing the access to the field.

That's a basic example about stateless, let's suppose you have a class that only performs the sum operation:

public class StatelessClass{

    public int sum(int a, int b){
        return a+b;
    }

}

In the same way, you can declare it as a abstract class (no instantiable itself) and make its methods static, which means you don't need any instance of it to call its methods:

public abstract class StatelessClass{

    /**
    *   I only sum objects
    */
    public static int sum(int a, int b){
        return a+b;
    }

}

Then you can use it as StatelessClass.sum(1,1);, this actually would be very similar to have a Singleton object itself, with the difference that in the Singleton you have a unique instance shared in the application.

In the same way, having a field which is injected and provides access to a service neither is considered to alter the state of the object:

public class StatelessServiceClass{

    private Service service;

    public int sum(int a, int b){
        return service.sum(a,b);
    }

    public void setService(Service serv){
        this.service=serv;
    }

}

However, having a field which is modifiable makes the Object stateful:

public class StatefulClass{

    //This fields make the object STATEFUL
    private int totalSum = 0;

    public int sum(int a, int b){
        int sum = a + b;
        totalSum = totalSum + sum;
        if (totalSum > 100)
            System.out.println("This thread "+Thread.currentThread().getId()+
                +" got it!");
        return sum;
    }

}

As sum can be accessed by multiple threads at the same time, you should guarantee that totalSum is accessed in a synchronized way. The printed sentence is not guaranteed to be true unless you do it.

All of this is also properly explained in this answer's Threadsafety piece by @BalusC.

Every thread has its own copy of the Object o and so even if multiple threads call the method at the same time, each method call of Thread will have its own stack allocated and the logic will apply there.

Why is it Thread Safe?

Thread Stacks are private to them and are by default thread safe as no other thread can enter in others stack.

NOTE: You can say that this Singleton of yours is Thread safe but not that the application is Thread safe as it also depends on whether the Object o being passed is itself thread safe or not. But as far as safety of Singleton is concerned it is thread safe.

You can think about it in "pizza terms". You went to pizza cafe, and couple of other guys entered with you as well. Each one placed his order and then sat to his own table. Pizza boxes to be arrived then and each of you start eating his own meal.

Here, the cafe is a singleton, pizza boys are CPU cores, you and other customers are threads, orders and pizza are input and output data respectively, table is a piece of memory.

As you can see, each thread is served with his own piece of memory so CPU can distinguish your data and don't mix up. As you asked about stack, it's not a significant player here because each thread has it's own stack (as a part of your memory chunk).