There are some things wrong here and some other things that can be improved:

• "...object oriented languages encapsulate code into 'objects'.." When discussing object oriented languages or OO extensions to existing languages there are four concepts that need to be discussed conceptually - encapsulation, (data) abstraction, polymorphism and inheritance (see http://codebetter.com/raymondlewallen/2005/07/19/4-major-principles-of-object-oriented-programming/ for a long treatise on each). Perl offers interesting approaches to these concepts -- some of which are seen as OO heresy. Your code example shows data abstraction (for the state) without being clear that it really does not control access for example. It is easy to say $object_instance->{state} = 'bogus state';. A common assumption is that an object can hide its data from the outside world and force a user to manipulate it only in controlled ways. In Perl 5 you can violate that.
• An example that manually sets state makes little sense. If you had chosen a better example this might not have been an issue because it would have been obvious that it is probably a bad idea to create a setter for the internal state of your object! If we were talking about a washing machine object then it might accept commands to start/stop/etc. from the user and internally set its own state. Only a getter is needed for state and, preferably, should instead be in the form of named methods for important states, like, $object_instance->isCreated() for clarity.
• Your code example accepts @args in the constructor and then does nothing with them.
• Referencing the package is somewhat oversimplified. A popular error is this: Can't locate MyObject.pm in @INC (@INC contains:. When endeavoring to prepare people for OO use in Perl 5 it is helpful to mention that Perl needs to actually know where it might find MyObject.pm. It is really not suitable to leave people with the belief that they should be in the same directory as the script.
• Packages do not contain shebang lines.You don't run a package like you would a script and therefore that should not be in there.
• How do you know your code will compile? When developing code and putting it directly into packages it is easy to screw things up and not notice. You should do two things to avoid this: perl -c MyObject.pm to check the module code for errors and/or write tests for every method (run h2xs -AXn MyObject and look in the /t directory for examples).