Both of the localisation methods you mentioned are relative so they will drift over time as the errors accumulate. If you need accurate localisation over the long I would recommend looking into some form of absolute localisation as well.
To use encoders as a sensor to perform odometry you'll need to publish geometry_msgs/TwistWithCovarianceStamped describing the velocity of your robot. Your encoders measure wheel angular velocity directly so your first task will be to get your arduino making these measurements. When this is working you can use these rotation rates, the wheel diameters and separation distance to calculate the linear and angular velocity of your robot. You'll need to make a rough estimate of a constant value for the co-variance of these values, then you can construct and publish the twist message described above.
You then have two choices. You can integrate this velocity yourself to determine the robots position relative to its starting point, or you can use an existing ros package such as robot_localization to do the job for you.
Regarding the IMU, there are existing packages such as razor_imu_9dof that can do the job for you. I really recommend looking into them because it's not a trivial task.
