If it's tidally locked to the sun, by definition there's no such thing as axial tilt. That can be disregarded.
The first thing is to not think of latitude and longitude in the way it's oriented on Earth. For simplicity, we'll assume the same numbering system as on Earth (360 degrees = full circle), and for timekeeping, we'll assume one orbit around the sun is 100 days (Earth standard).
The center of your navigational grid on the lit side is going to be the sun. Directly overhead marks the zero position, the hot pole. Instead of 90 degrees, it's going to be labelled 0. The terminator--ignoring atmospheric diffraction of light--is going to be 90. That's going to be your latitude. On the daylight side, easy to find; you simply use a sextant to measure the height of the sun over the horizon, and better than the Earth, you don't have to wait until midday to do it; you can do it at any time.
On the cold side, you rotate the grid. Now, your reference is a recognizable star or constellation closest to your planet's orbital axis, so it's the closest thing to unmoving you can find in the sky. Essentially, instead of finding a pole star for your planet's rotation as on Earth, you find it for your planet's revolution around the sun. Find one above and below the orbital plane, and you've got a way of determining stellar latitude by measuring the distance of one (or other features, as the sky is mapped) above the horizon.
Picture it this way: Imagine that on the Eurasian side of the Earth, latitude and longitude are exactly like they are now, but on the side with the Americas, it's turned sideways so that the "pole" is centered on the Galapagos islands. Now 90 degrees latitude, as centered on the Galapagos, would be the same great circle around the planet as 0/180 degrees longitude based on the Eurasian Grid. The Eurasian side is the dark side of the planet, the Galapagos side the light side.
Okay, so on the Eurasian night side, further measurement is relatively easy, once you've invented reasonably accurate timekeeping mechanism (ie, clocks). You've got astro-north, and astro-south. You know that stars near the astro-equator (which would be the plane of the planet's orbit) take a half-year (50 days) to go from horizon to horizon. At day 1, it rises above the horizon, is at its apex at day 25, and set on day 50.
If you have accurate timekeeping, you know that at a specified location at a given date a given star should be a certain number of degrees above the horizon. If you measure the height, you can measure the difference between where it is and where it should be on a given date as seen from your latitude, and that can be used to calculate the longitude.
Now, this only works if you have accurate timekeeping devices so you know your date/time compared to the reference point, but really, not a lot of difference from the problem of measuring longitude on Earth before the advent of accurate portable clocks.
On the day side, it's trickier. Solar latitude is trivial to determine, as mentioned. Solar longitude becomes harder without the stars. You're initial assumption (with the sun "bobbing" up and down, as seen from the planet) would make it easier, but that can't happen if the planet is tidally locked.
